Concise 1 pass JAVA solution


  • 3

    The basic idea is using two pointers: left boundary, right boundary. Then

    1) put 0 to the left of the left boundary;    
    2) put 2 to the right of the right boundary.
    

    As the following:

     left boundary|         |right boundary
            00000 | 1111111 | 22222222
    

    JAVA Code: Time complexity O(n)

    As each element is only checked once, so the time complexity should be O(n).

    public void sortColors(int[] nums) { 
        if (nums == null || nums.length == 0) return;
        int left = 0, right = nums.length - 1;// Left, right boundary
        for (int i = 0; i <= right; i++) {
        	if (nums[i] == 0 && i != left)// Only swap if i != left
        		swap(nums, i--, left++);
        	else if (nums[i] == 2 && i != right)// Only swap if i != right 
        		swap(nums, i--, right--);        	
        }        
    }
    void swap(int[] nums, int i, int j) {
    	int tmp = nums[i];
    	nums[i] = nums[j];
    	nums[j] = tmp;
    }

  • 1
    E
    public class Solution {
        public void sortColors(int[] nums) {
            int l = 0, r = nums.length - 1;
            for (int i = 0; i <= r; i++) {
                if (nums[i] == 0) {
                    swap(nums, i, l++);
                } else if (nums[i] == 2) {
                    swap(nums, i--, r--);
                }
            }
        }
        public void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
    

    This works fine. Do we really need to check that many conditions?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.