A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 905. Sort Array By Parity, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are sortArrayByParity.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(NlogN), where N is the length of A.
- Space: O(N) for the sort, depending on the built-in implementation of sort.
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.
03
04You may return any answer array that satisfies this condition.
05
06
07
08Example 1:
09
10Input: [3,1,2,4]
11Output: [2,4,3,1]
12The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
13
14
15Note:
16
171 <= A.length <= 5000
180 <= A[i] <= 5000
19**/
20
21/**
22Solution
23Approach 1: Sort
24Intuition and Algorithm
25
26Use a custom comparator when sorting, to sort by parity.
27
28//Java
29class Solution {
30 public int[] sortArrayByParity(int[] A) {
31 int[] ans = new int[A.length];
32 int t = 0;
33
34 for (int i = 0; i < A.length; ++i)
35 if (A[i] % 2 == 0)
36 ans[t++] = A[i];
37
38 for (int i = 0; i < A.length; ++i)
39 if (A[i] % 2 == 1)
40 ans[t++] = A[i];
41
42 return ans;
43 }
44}
45
46Complexity Analysis
47
48Time Complexity: O(NlogN), where N is the length of A.
49
50Space Complexity: O(N) for the sort, depending on the built-in implementation of sort.
51**/
52
53/**
54Approach 2: Two Pass
55Intuition and Algorithm
56
57Write all the even elements first, then write all the odd elements.
58
59//Java
60class Solution {
61 public int[] sortArrayByParity(int[] A) {
62 int[] ans = new int[A.length];
63 int t = 0;
64
65 for (int i = 0; i < A.length; ++i)
66 if (A[i] % 2 == 0)
67 ans[t++] = A[i];
68
69 for (int i = 0; i < A.length; ++i)
70 if (A[i] % 2 == 1)
71 ans[t++] = A[i];
72
73 return ans;
74 }
75}
76
77Complexity Analysis
78
79Time Complexity: O(N), where N is the length of A.
80
81Space Complexity: O(N), the space used by the answer.
82**/
83
84//Your runtime beats 39.93 % of cpp submissions.
85/**
86class Solution {
87public:
88 vector<int> sortArrayByParity(vector<int>& A) {
89 vector<int> odd;
90 vector<int> even;
91 for(int i = 0; i < A.size(); i++){
92 if(A[i]%2==0){
93 even.push_back(A[i]);
94 }else{
95 odd.push_back(A[i]);
96 }
97 }
98 even.insert(even.end(), odd.begin(), odd.end());
99 return even;
100 }
101};
102**/
103
104/**
105Approach 3: In-Place
106Intuition
107
108If we want to do the sort in-place, we can use quicksort, a standard textbook algorithm.
109
110Algorithm
111
112We'll maintain two pointers i and j. The loop invariant is everything below i has parity 0 (ie. A[k] % 2 == 0 when k < i), and everything above j has parity 1.
113
114Then, there are 4 cases for (A[i] % 2, A[j] % 2):
115
116If it is (0, 1), then everything is correct: i++ and j--.
117
118If it is (1, 0), we swap them so they are correct, then continue.
119
120If it is (0, 0), only the i place is correct, so we i++ and continue.
121
122If it is (1, 1), only the j place is correct, so we j-- and continue.
123
124Throughout all 4 cases, the loop invariant is maintained, and j-i is getting smaller. So eventually we will be done with the array sorted as desired.
125
126Complexity Analysis
127
128Time Complexity: O(N), where N is the length of A. Each step of the while loop makes j-i decrease by at least one. (Note that while quicksort is O(NlogN) normally, this is O(N) because we only need one pass to sort the elements.)
129
130Space Complexity: O(1) in additional space complexity.
131**/
132
133//Your runtime beats 63.15 % of cpp submissions.
134class Solution {
135public:
136 vector<int> sortArrayByParity(vector<int>& A) {
137 int i = 0;
138 int j = A.size()-1;
139 while(i < j){
140 if(A[i]%2 > A[j]%2){
141 int tmp = A[i];
142 A[i] = A[j];
143 A[j] = tmp;
144 }
145 if(A[i]%2==0)i++;
146 if(A[j]%2==1)j--;
147 }
148 return A;
149 }
150};Cost
Complexity
Time
O(NlogN), where N is the length of A.
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(N) for the sort, depending on the built-in implementation of sort.
Auxiliary state plus the answer structure where the problem requires one.