Let's make this one less mysterious. For 908. Smallest Range I, 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.
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 smallestRangeI.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- 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:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
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
01/**
02Given an array A of integers, for each integer A[i] we may choose any x with -K <= x <= K, and add x to A[i].
03
04After this process, we have some array B.
05
06Return the smallest possible difference between the maximum value of B and the minimum value of B.
07
08
09
10Example 1:
11
12Input: A = [1], K = 0
13Output: 0
14Explanation: B = [1]
15Example 2:
16
17Input: A = [0,10], K = 2
18Output: 6
19Explanation: B = [2,8]
20Example 3:
21
22Input: A = [1,3,6], K = 3
23Output: 0
24Explanation: B = [3,3,3] or B = [4,4,4]
25
26
27Note:
28
291 <= A.length <= 10000
300 <= A[i] <= 10000
310 <= K <= 10000
32**/
33
34//Your runtime beats 98.55 % of cpp submissions.
35class Solution {
36public:
37 int smallestRangeI(vector<int>& A, int K) {
38 return max(*max_element(A.begin(), A.end())-*min_element(A.begin(), A.end())-2*K,0);
39 }
40};
41
42/**
43Solution
44Approach 1: Mathematical
45Intuition and Algorithm
46
47Let A be the original array, and B be the array after all our modifications.
48Towards trying to minimize max(B) - min(B),
49let's try to minimize max(B) and maximize min(B) separately.
50
51The smallest possible value of max(B) is max(A) - K, as the value max(A) cannot go lower.
52Similarly, the largest possible value of min(B) is min(A) + K.
53So the quantity max(B) - min(B) is at least ans = (max(A) - K) - (min(A) + K).
54
55We can attain this value (if ans >= 0), by the following modifications:
56
57If A[i] <= min(A) + KA[i]≤min(A)+K, then B[i] = min(A) + KB[i]=min(A)+K
58Else, if A[i] >= max(A) - KA[i]≥max(A)−K, then B[i] = max(A) - KB[i]=max(A)−K
59Else, B[i] = A[i]B[i]=A[i].
60If ans < 0, the best answer we could have is ans = 0, also using the same modification.
61
62Complexity Analysis
63
64Time Complexity: O(N), where N is the length of A.
65
66Space Complexity: O(1).
67**/Cost