DSA: Arrays 1: One Dimensional
10 min read
Array Problem Patterns
Max Subarray Sum · Range Update Queries · Merge Intervals
A problem-solving loop and three array patterns — moving from brute force to an optimal solution, one step at a time.
Contents
1. How to Approach Any DSA Problem
2. Maximum Subarray Sum
3. Range Update Queries — Add From an Index
4. Range Update Queries — Add Between Two Indices
5. Merge Overlapping Intervals
6. One-Page Revision
1. How to Approach Any DSA Problem
Every problem below is attacked the same way. Fix this loop first, because the same checklist is what tells you when a brute-force idea is good enough and when it must be optimised.
1. Start a timer for the attempt (about 35 minutes) so you commit to thinking, not stalling.
2. Read the problem and make sure you understand exactly what is being asked.
3. Form a solution / logic for it.
4. Check the solution against the time limit (TLE) and the corner cases.
○ If it clears both — move on to the next problem.
○ If it does not — set the problem aside to revisit later: review your notes and any available hints, then re-attempt it.
The loop in one line: timer → understand → solve → check TLE + corner cases → move on, or revisit later. |
2. Maximum Subarray Sum
2.1 The problem
Given an integer array arr[N], find the maximum sum among all of its subarrays. A subarray is a contiguous part of the array.
Example 1 — the best subarray is 3, 4, -1, 5, giving a maximum sum of 11:
0 | 1 | 2 | 3 | 4 | 5 | 6 |
-2 | 3 | 4 | -1 | 5 | -10 | 7 |
Example 2 — the best subarray is 4, 6, 8, giving a maximum sum of 18:
0 | 1 | 2 | 3 | 4 | 5 | 6 |
-3 | 4 | 6 | 8 | -10 | 2 | 7 |
Quick checks: for [4, 5, 2, 1, 6] the answer is 18 (every element is positive, so take them all); for [-4, -3, -6, -9, -2] the answer is -2 (every element is negative, so the best you can do is the single largest element).
2.2 Brute force — try every subarray → O(N³)
An array with N elements has N × (N + 1) ÷ 2 subarrays. |
The most direct idea: pick every start i and every end j, add up the elements in between, and keep the best sum seen.
ans = -infinity for (i = 0; i <= N-1; i++) // start of subarray for (j = i; j <= N-1; j++) // end of subarray sum = 0 for (k = i; k <= j; k++) // add arr[i..j] sum = sum + arr[k] ans = max(ans, sum) return ans |
TC: O(N³) · SC: O(1)
Walking the subarrays that start at index 0 of [1, 2, 3, 4]: [0,0] = 1, [0,1] = 3, [0,2] = 6, [0,3] = 10; then the starts at index 1 give [1,1], [1,2], [1,3]; index 2 gives [2,2], [2,3]; index 3 gives [3,3].
2.3 Drop the inner loop — extend the running sum → O(N²)
Because of the brute force above, notice the innermost loop rebuilds the sum from scratch every time. Instead, as j moves one step to the right, just add arr[j] to the sum you already have.
ans = -infinity for (i = 0; i <= N-1; i++) sum = 0 for (j = i; j <= N-1; j++) sum = sum + arr[j] // extend, don't recompute ans = max(ans, sum) return ans |
TC: O(N²) · SC: O(1)
On [-3, 4, 6, 8, -10, 2, 7] this still returns 18 (the block 4, 6, 8).
2.4 Reading the sign pattern (building the intuition)
Before the fast method, look at how the answer depends on where the negatives sit:
1. All positive → the answer is the sum of every element. Example: [4, 2, 1, 6, 7].
2. All negative → the answer is the single maximum (largest) element. Example: [-4, -8, -9, -3, -5].
3. Negatives on both ends, positives in the middle → the answer is the sum of the positive block.
4. Negatives only on the left or only on the right → again the answer is the sum of the positive block.
5. Mixed (+ + + − − + +) → not obvious by eye; this is what the general method handles.
2.5 Kadane's method — reset when negative → O(N)
From those patterns: a running sum that has gone negative can only drag down whatever comes after it, so the moment the running sum drops below 0 we throw it away (reset to 0) and start fresh from the next element.
Dry run on [-20, 10, -20, -12, 6, 5, -3, 8, -2]:
Step (running total) | Value | Action |
|---|---|---|
sum = -20 | -20 | negative → reset to 0 |
sum = 10 | 10 | keep |
sum = 10 - 20 = -10 | -10 | negative → reset to 0 |
sum = 0 - 12 = -12 | -12 | negative → reset to 0 |
sum = 0 + 6 = 6 | 6 | keep |
sum = 6 + 5 = 11 | 11 | keep |
sum = 11 + (-3) = 8 | 8 | keep |
sum = 8 + 8 = 16 | 16 | keep ← maximum |
sum = 16 + (-2) = 14 | 14 | keep |
The largest running total reached is 16, so the answer is 16.
A second dry run on [-2, 3, 4, -1, 5, -10, 7] gives running totals 0, 3, 7, 6, 11, 1, 8 — maximum 11.
Edge case — all negatives. If every element is negative, resetting to 0 never lets the sum turn positive, so you would wrongly report 0. Track maxSum separately, starting at -∞, and update it before the reset. That way [-4, -5, -6] correctly returns -4 (the largest element). |
int maxSubarraySum(arr, n) { maxSum = -infinity // INT_MIN sum = 0 for (i = 0; i <= n-1; i++) { sum = sum + arr[i] maxSum = max(maxSum, sum) if (sum < 0) sum = 0 } return maxSum } |
TC: O(N) · SC: O(1)
3. Range Update Queries — Add From an Index
3.1 The problem
Given an array arr[N] initially filled with all 0s, apply Q queries and return the final array. Each query is (i, x): add x to every element from index i to the end of the array.
Example — arr of size 7 (all 0), queries (1, 3), (4, -2), (3, 1). Adding 3 from index 1, then -2 from index 4, then 1 from index 3 gives:
0 | 1 | 2 | 3 | 4 | 5 | 6 |
0 | 3 | 3 | 4 | 2 | 2 | 2 |
Quiz: A = [0, 0, 0, 0, 0] with Query(1, 3), Query(0, 2), Query(4, 1) → [2, 5, 5, 5, 6].
3.2 Brute force → O(Q·N)
Do exactly what each query says: for every query, walk from index i to the end and add x. With Q queries each touching up to N elements, this is Q × N work — too slow when both are large.
TC: O(Q × N) · SC: O(1)
3.3 Mark once, then prefix-sum → O(Q + N)
Because adding x from index i to the end is the same for every index at or after i, we do not touch each of them. Instead we mark +x once at index i, and at the very end sweep a running (prefix) sum left to right — the mark then flows rightward into every later index automatically.
Queries (1, 3), (4, -2), (3, 1) become the mark array [0, 3, 0, 1, -2, 0, 0]:
0 | 1 | 2 | 3 | 4 | 5 | 6 |
0 | 3 | 0 | 1 | -2 | 0 | 0 |
Running the prefix sum over that mark array reproduces the answer [0, 3, 3, 4, 2, 2, 2].
0 | 1 | 2 | 3 | 4 | 5 | 6 |
0 | 3 | 3 | 4 | 2 | 2 | 2 |
void performQueries(arr, n, q) { for (i = 0; i < q.length; i++) { // Q marks index = q[i][0] val = q[i][1] arr[index] = arr[index] + val } for (i = 1; i <= n-1; i++) // prefix sum arr[i] = arr[i] + arr[i-1] } |
TC: O(Q + N) · SC: O(1)
4. Range Update Queries — Add Between Two Indices
4.1 The problem
Same setup — arr[N] initially all 0s, Q queries, return the final array — but now each query is (i, j, x): add x to every element from index i to index j, inclusive.
Example — arr of size 7 (all 0), queries (1, 3, 2), (2, 5, 3), (5, 6, -1):
0 | 1 | 2 | 3 | 4 | 5 | 6 |
0 | 2 | 5 | 5 | 3 | 2 | -1 |
Quiz: arr of size 8 (all 0) with (1, 4, 3), (0, 5, -1), (2, 2, 4), (4, 6, 3) → [-1, 2, 6, 2, 5, 2, 3, 0].
4.2 Difference array — turn the effect on, then off → O(Q + N)
Reuse the mark-and-prefix-sum idea from Section 3, with one extra step per query: the addition must stop after index j. So mark +x at index i to switch the effect on, and mark -x at index j+1 to switch it off, then prefix-sum once at the end.
One extra step in each query: add (-x) at arr[j+1] to nullify the effect for indices j+1 onward. Only write it when j+1 is inside the array (j + 1 ≤ N - 1). |
For query (1, 3, 2): mark +2 at index 1 and -2 at index 4, giving [0, 2, 0, 0, -2, 0, 0]. Its prefix sum, [0, 2, 2, 2, 0, 0, 0], adds 2 to indices 1, 2, 3 only — exactly the requested range.
void performQueries(arr, n, q) { for (i = 0; i < q.length; i++) { index1 = q[i][0] index2 = q[i][1] val = q[i][2] arr[index1] = arr[index1] + val if (index2 + 1 <= n-1) arr[index2 + 1] = arr[index2 + 1] - val } for (i = 1; i <= n-1; i++) // prefix sum arr[i] = arr[i] + arr[i-1] } |
TC: O(Q + N) · SC: O(1)
5. Merge Overlapping Intervals
5.1 Intervals and overlap
An interval is a (start, end) pair, for example (5, 8). Two intervals overlap when they share any point. Some cases:
Interval 1 | Interval 2 | Overlap? | Merged result |
|---|---|---|---|
(2, 6) | (3, 7) | yes | (2, 7) |
(2, 8) | (4, 6) | yes | (2, 8) |
(1, 3) | (4, 7) | no | — |
(1, 3) | (3, 5) | yes | (1, 5) |
Way to merge two overlapping intervals: ( min(s1, s2), max(e1, e2) ). |
5.2 The problem
Given intervals sorted by their start time, merge all the overlapping ones. Example input and output:
Input: (0, 2), (1, 4), (5, 6), (6, 8), (7, 10), (8, 9), (12, 14)
Output: (0, 4), (5, 10), (12, 14)
5.3 Sweep with a current interval
Because the intervals are already sorted by start, keep a current interval (currStart, currEnd) and scan left to right. The next interval overlaps when its start is ≤ currEnd; then extend currEnd = max(currEnd, its end). When it does not overlap, the current interval is finished — push it to the answer and open a new current interval.
Current | Next | Overlap? | Answer so far |
|---|---|---|---|
(0, 2) | (1, 4) | yes | current becomes (0, 4) |
(0, 4) | (5, 6) | no | add (0, 4); current = (5, 6) |
(5, 6) | (6, 8) | yes | current becomes (5, 8) |
(5, 8) | (7, 10) | yes | current becomes (5, 10) |
(5, 10) | (8, 9) | yes | current stays (5, 10) |
(5, 10) | (12, 14) | no | add (5, 10); current = (12, 14) |
After the loop, add the last current interval, giving (0, 4), (5, 10), (12, 14).
mergeIntervals(A, n) { currStart = A[0][0] currEnd = A[0][1] for (i = 1; i <= n-1; i++) { // check if they're overlapping if (A[i][0] <= currEnd) { // when they overlap currEnd = max(currEnd, A[i][1]) } else { ans.add( pair(currStart, currEnd) ) currStart = A[i][0] currEnd = A[i][1] } } ans.add( pair(currStart, currEnd) ) // add the last interval return ans } |
Note: you only add to the answer when you cannot merge. While you can merge, you just keep extending currEnd — and the final interval is added once after the loop ends. |
6. One-Page Revision
The whole chain, compressed — built only from the sections above.
Pattern | Key idea | Complexity |
|---|---|---|
Approach loop | timer → understand → solve → check TLE + corner cases → move on or revisit | — |
Max subarray (brute) | try all N×(N+1)÷2 subarrays, sum each | O(N³) |
Max subarray (better) | extend the running sum instead of recomputing | O(N²) |
Max subarray (Kadane) | keep a running sum; reset to 0 when it goes negative; track maxSum from -∞ for the all-negative case | O(N) |
Add from index i | mark +x at i, then prefix-sum the array | O(Q + N) |
Add over [i, j] | mark +x at i and -x at j+1, then prefix-sum | O(Q + N) |
Merge intervals | given sorted starts, extend currEnd while start ≤ currEnd, else close; merge = (min start, max end) | — |