codes/15-75. Sort Colors at main · ashish-commit987/codes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// class Solution {
//     public void sortColors(int[] nums) {
//         int x=0;
//         int y=0;
//         int z=0;
//         for(int i=0;i<nums.length;i++){
//             if(nums[i]==0){
//                 x++;
//             }
//             else if(nums[i]==1){
//                 y++;
//             }
//             else{
//                 z++;
//             }
//         }
//         for(int i=0;i<x;i++){
//             nums[i]=0;
//         }
//         for(int i=x;i<x+y;i++){
//             nums[i]=1;
//         }
//         for(int i=x+y;i<x+y+z;i++){
//             nums[i]=2;
//         }
//     }
// }

// optimal solution

class Solution {


    public void sortColors(int[] nums) {
        int n=nums.length;
        int mid=0;
        int high=n-1;
        int low=0;
        while(mid<=high){
            if(nums[mid]==0){
                int temp=nums[low];
                nums[low]=nums[mid];
                nums[mid]=temp;
                mid++;
                low++;
            }
            else if(nums[mid]==1){
                mid++;
            }
            else{
                int temp=nums[mid];
                nums[mid]=nums[high];
                nums[high]=temp;


                high--;
            }
        }
    }
}

https://leetcode.com/problems/sort-colors/