The trick here is to name the state correctly, then let the implementation follow. For 922. Sort Array By Parity II, the solution in this repository is mainly a sliding window solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. 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: sliding window.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are sortArrayByParityII.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- 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(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.
03
04Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.
05
06You may return any answer array that satisfies this condition.
07
08
09
10Example 1:
11
12Input: [4,2,5,7]
13Output: [4,5,2,7]
14Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.
15
16
17Note:
18
192 <= A.length <= 20000
20A.length % 2 == 0
210 <= A[i] <= 1000
22**/
23
24//Your runtime beats 28.06 % of cpp submissions.
25class Solution {
26public:
27 vector<int> sortArrayByParityII(vector<int>& A) {
28 int evenix = 0;
29 int oddix = 1;
30 //use evenix to scan the even part of A, oddix to scan odd part of A
31 while(evenix<A.size() && oddix<A.size()){
32 if(A[evenix]%2==1 && A[oddix]%2==0){
33 //swap
34 int tmp = A[evenix];
35 A[evenix] = A[oddix];
36 A[oddix] = tmp;
37 evenix+=2;
38 oddix+=2;
39 }
40 if(A[evenix]%2==0){
41 evenix+=2;
42 }
43 if(A[oddix]%2==1){
44 oddix+=2;
45 }
46 }
47 return A;
48 }
49};
50
51/**
52Solution
53Approach 1: Two Pass
54Intuition and Algorithm
55
56Read all the even integers and put them into places ans[0], ans[2], ans[4], and so on.
57
58Then, read all the odd integers and put them into places ans[1], ans[3], ans[5], etc.
59**/
60
61//Java
62/**
63class Solution {
64 public int[] sortArrayByParityII(int[] A) {
65 int N = A.length;
66 int[] ans = new int[N];
67
68 int t = 0;
69 for (int x: A) if (x % 2 == 0) {
70 ans[t] = x;
71 t += 2;
72 }
73
74 t = 1;
75 for (int x: A) if (x % 2 == 1) {
76 ans[t] = x;
77 t += 2;
78 }
79
80 return ans;
81 }
82}
83**/
84
85/**
86Complexity Analysis
87
88Time Complexity: O(N), where N is the length of A.
89
90Space Complexity: O(N).
91**/
92
93/**
94Approach 2: Read / Write Heads
95Intuition
96
97We are motivated (perhaps by the interviewer) to pursue a solution where we modify the original array A in place.
98
99First, it is enough to put all even elements in the correct place, since all odd elements will be in the correct place too. So let's only focus on A[0], A[2], A[4], ...
100
101Ideally, we would like to have some partition where everything to the left is already correct, and everything to the right is undecided.
102
103Indeed, this idea works if we separate it into two slices even = A[0], A[2], A[4], ... and odd = A[1], A[3], A[5], .... Our invariant will be that everything less than i in the even slice is correct, and everything less than j in the odd slice is correct.
104
105Algorithm
106
107For each even i, let's make A[i] even. To do it, we will draft an element from the odd slice. We pass j through the odd slice until we find an even element, then swap. Our invariant is maintained, so the algorithm is correct.
108
109**/
110
111//Your runtime beats 22.25 % of cpp submissions.
112class Solution {
113public:
114 vector<int> sortArrayByParityII(vector<int>& A) {
115 int evenix = 0;
116 int oddix = 1;
117
118 for(int evenix = 0; evenix < A.size(); evenix+=2){
119 if(A[evenix]%2==1){
120 while(A[oddix]%2==1)
121 oddix+=2;
122 int tmp = A[evenix];
123 A[evenix] = A[oddix];
124 A[oddix] = tmp;
125 }
126 }
127 return A;
128 }
129};
130
131/**
132Complexity Analysis
133
134Time Complexity: O(N), where N is the length of A.
135
136Space Complexity: O(1).
137**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.