This problem looks busy at first, but the accepted solution is built around one steady invariant. For 665. Non-decreasing Array, the solution in this repository is mainly a straightforward implementation 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: straightforward implementation.
The notes already sitting in the source point us in the right direction:
- WA
- 311 / 325 test cases passed.
- [3,4,2,3] should be false
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are checkPossibility, monotone_increasing, brute_force.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- 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:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
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), start and end look an element at most once, and the remaining length of subarray is at most 4
- Space: O(1), the length of subarray passed to brute_force is at most 4
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//WA
02//311 / 325 test cases passed.
03//[3,4,2,3] should be false
04class Solution {
05public:
06 bool checkPossibility(vector<int>& nums) {
07 int violate_count = 0;
08 for(int i = 1; i < nums.size(); i++){
09 if(nums[i] < nums[i-1]){
10 violate_count++;
11 }
12 }
13 // cout << violate_count << endl;
14 return violate_count <= 1;
15 }
16};
17
18//Approach #1: Brute Force
19//time: O(N^2), space: O(1)
20//Runtime: 128 ms, faster than 6.85% of C++ online submissions for Non-decreasing Array.
21//Memory Usage: 27.2 MB, less than 12.55% of C++ online submissions for Non-decreasing Array.
22class Solution {
23public:
24 bool monotone_increasing(vector<int>& nums){
25 int n = nums.size();
26
27 for(int i = 1; i < n; ++i){
28 if(nums[i-1] > nums[i]){
29 return false;
30 }
31 }
32
33 return true;
34 }
35
36 bool checkPossibility(vector<int>& nums) {
37 int n = nums.size();
38
39 for(int i = 0; i < n; ++i){
40 int old = nums[i];
41 nums[i] = (i-1 >= 0) ? nums[i-1] : INT_MIN;
42 if(monotone_increasing(nums)){
43 return true;
44 }
45 nums[i] = old;
46 }
47
48 return false;
49 }
50};
51
52//Approach #2: Reduce to Smaller Problem
53//time: O(N), start and end look an element at most once, and the remaining length of subarray is at most 4
54//space: O(1), the length of subarray passed to brute_force is at most 4
55//Runtime: 60 ms, faster than 81.80% of C++ online submissions for Non-decreasing Array.
56//Memory Usage: 27.2 MB, less than 16.47% of C++ online submissions for Non-decreasing Array.
57class Solution {
58public:
59 bool monotone_increasing(vector<int>& nums){
60 int n = nums.size();
61
62 for(int i = 1; i < n; ++i){
63 if(nums[i-1] > nums[i]){
64 return false;
65 }
66 }
67
68 return true;
69 }
70
71 bool brute_force(vector<int> nums) {
72 int n = nums.size();
73
74 for(int i = 0; i < n; ++i){
75 int old = nums[i];
76 nums[i] = (i-1 >= 0) ? nums[i-1] : INT_MIN;
77 if(monotone_increasing(nums)){
78 return true;
79 }
80 nums[i] = old;
81 }
82
83 return false;
84 }
85
86 bool checkPossibility(vector<int>& nums) {
87 int n = nums.size();
88
89 int start = 0, end = n-1;
90
91 while(start+2 < n && nums[start] <= nums[start+1] && nums[start+1] <= nums[start+2]){
92 ++start;
93 }
94
95 //remove duplicate checking by "end-2 >= 0" -> "end-2 >= start"
96 while(end-2 >= start && nums[end-2] <= nums[end-1] && nums[end-1] <= nums[end]){
97 --end;
98 }
99
100 int len = end-start+1;
101 // cout << start << ", " << end << ", " << len << endl;
102 if(len <= 2){
103 /*
104 the while loop continues when the length of subarray >= 3,
105 so if it exit with length <= 2,
106 it means that there are no wrong elements
107 */
108 return true;
109 }else if(len >= 5){
110 /*
111 consider [1,3,2,4,2],
112 start and end will be 0 and 4,
113 we need to revise one element in nums[0...2] and
114 another element in nums[2...4],
115 so it's invalid
116 */
117 return false;
118 }
119
120 return brute_force(vector<int>(nums.begin()+start, nums.begin()+start+len));
121 }
122};
123
124//Approach #3: Locate and Analyze Problem Index
125//time: O(N), space: O(1)
126//Runtime: 56 ms, faster than 92.01% of C++ online submissions for Non-decreasing Array.
127//Memory Usage: 27.1 MB, less than 39.78% of C++ online submissions for Non-decreasing Array.
128class Solution {
129public:
130 bool checkPossibility(vector<int>& nums) {
131 int n = nums.size();
132 int pos = -1;
133
134 //find nums[i] and nums[i+1] s.t. nums[i] > nums[i+1]
135 for(int i = 0; i+1 < n; ++i){
136 if(nums[i] > nums[i+1]){
137 if(pos == -1){
138 pos = i;
139 }else{
140 //if we find 2 or more such i, then it's impossible
141 return false;
142 }
143 }
144 }
145
146 /*
147 pos == -1: no such i, so it's definitely possible
148 pos == 0 or pos+1 == n-1, the two elements are at the edge,
149 can make it good by setting nums[pos+1] = nums[pos]
150
151 otherwise, pos-1, pos, pos+1, pos+2 all exist,
152 we can
153 (1) change nums[pos] to nums[pos-1],
154 e.g. [1,3,2,4], pos = 1, change it to [1,1,2,4]
155 or
156 (2) change nums[pos+1] to nums[pos],
157 e.g. [1,2,4,3], pos = 1, change to to [1,2,2,3]
158
159 fail case:
160 e.g. [4,6,2,3], pos = 1, since 4>2 and 6>3,
161 we cannot just change one element
162 */
163
164 return (pos == -1) || (pos == 0) || (pos+1 == n-1) || (nums[pos-1] <= nums[pos+1]) || (nums[pos] <= nums[pos+2]);
165 }
166};Cost
Complexity
Time
O(N), start and end look an element at most once, and the remaining length of subarray is at most 4
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(1), the length of subarray passed to brute_force is at most 4
Auxiliary state plus the answer structure where the problem requires one.