LeetCode-Problems/Sort Colors at main · tarungupta1/LeetCode-Problems · 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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
Problem Number: 75
Problem Name: Sort Colors
Link: https://leetcode.com/problems/sort-colors/

Question
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order
red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.


Time Complexity: O(N), where N is the number of elements
Space Complexity: O(1)


Solution

APPROACH 1
class Solution {
public:
    void sortColors(vector<int>& arr) {

        /* here partitioning of colors will be like:  [ 0 0 .. 0 1 1 .. 1 2 2 .. 2 ? ? .. ? ]
                                                                 ↑        ↑        ↑
                                                             zeroidx   oneidx      i (unknown)
          So, [0, zeroidx-1] => 0
              [zeroidx, oneidx-1] => 1
              [oneidx, i-1] => 2
              [i, n-1] => unknown
        */

        int n=arr.size();
        int zeroidx=0, oneidx=0;
        for(int i=0; i<n; i++){
            // if we find 0, then we will first swap (i and zeroidx) and then swap (i and oneidx) and increement 'zeroidx' and 'oneidx' indexes
            if(arr[i] == 0){
                int temp = arr[i];
                arr[i] = arr[oneidx];
                arr[oneidx] = arr[zeroidx];
                arr[zeroidx] = temp;
                zeroidx++;
                oneidx++;
            }
            // if we find 1, then we will swap (i and oneidx) and increement 'oneidx' index
            else if(arr[i] == 1){
                int temp = arr[i];
                arr[i] = arr[oneidx];
                arr[oneidx] = temp;
                oneidx++;
            }
            // if we find 2, we will just move ahead
        }
    }
};


APPROACH 2
class Solution {
public:
    void sortColors(vector<int>& arr) {

        /* here partitioning of colors will be like:  [ 0 0 .. 0 1 1 .. 1 ? ? ? ...... ? 2 2 .. 2 ]
                                                                 ↑        ↑            ↑
                                                               zero     one(unknown)   two
          So, [0, zero-1] => 0
              [zero, one-1] => 1
              [one, two] => unknown
              [two+1, n-1] => 2
        */

        int n = arr.size();
        int zero = 0, one = 0, two = n-1;
        while(one <= two){
            // if we find 0, then we will swap (zero and one) and increement 'zero' and 'one' indexes
            if(arr[one] == 0){
                int temp = arr[one];
                arr[one] = arr[zero];
                arr[zero] = temp;
                one++;
                zero++;
            }
            // if we find 1, then we will increement 'one' index
            else if(arr[one] == 1){
                one++;
            }
            // if we find 2, then we will swap (one and two) and decreement 'two' index
            else{
                int temp = arr[one];
                arr[one] = arr[two];
                arr[two] =temp;
                two--;
            }
        }
    }
};