Usually you can read the time complexity straight off the loops. But some algorithms have a step whose cost varies: cheap most of the time, expensive now and then. Multiplying the worst single step by n then gives a bound that is far too pessimistic. Amortized analysis instead bounds the total work of all the steps together. Every algorithm in this chapter has a loop inside a loop and still runs in O(n), because something can only happen n times in total.
Aam taur pe time complexity loops dekh ke hi pata chal jaati hai. Par kuch algorithms mein ek step ki cost badalti rehti hai — zyaadatar sasta, kabhi-kabhi mehenga. Tab sabse mehenge step × n wala bound bahut zyada pessimistic hota hai. Amortized analysis iski jagah saare steps ke total kaam ko bound karta hai. Is chapter ke har algorithm mein loop ke andar loop hai, phir bhi O(n) — kyunki koi cheez total mein sirf n baar ho sakti hai.
8.1Two pointers method
In the two pointers method, two positions walk through the array, and each one only ever moves in one direction. Since each pointer moves at most n times, the whole walk is O(n), however the moves are spread out.
Subarray sum: given n positive numbers and a target x, find a subarray (a contiguous part) with sum x. Keep a window from L to R:
- On each turn, R moves right as long as the sum stays ≤ x.
- If the sum is exactly x, you’ve found it.
- Otherwise L moves one step right, and its value leaves the window.
For [1, 3, 2, 5, 1, 1, 2, 3] and x = 8, the window grows to 1 + 3 + 2 = 6 and gets stuck (adding 5 would overshoot), so L drops 1 and then 3. Then R takes 5 and 1, giving 2 + 5 + 1 = 8. On a single turn R might move many steps, but over the whole run it moves at most n steps in total.
Two pointers method mein do positions array pe chalti hain, aur dono sirf ek hi direction mein. Har pointer max n baar hilta hai, isliye poora walk O(n) — chahe moves kaise bhi bant-te hon.
Subarray sum: n positive numbers aur target x diye hain — sum x wala subarray (lagaatar hissa) dhundho. L se R tak ek window rakho:
- Har turn mein R tab tak right jaata hai jab tak sum ≤ x rahe.
- Sum theek x hai toh mil gaya.
- Warna L ek step right, aur uski value window se bahar.
[1, 3, 2, 5, 1, 1, 2, 3] aur x = 8 pe window 1 + 3 + 2 = 6 tak badhti hai aur atak jaati hai (5 lene se zyada ho jaata), toh L pehle 1 aur phir 3 chhodta hai. Phir R 5 aur 1 leta hai: 2 + 5 + 1 = 8. Ek turn mein R kai steps chal sakta hai, par poore run mein total max n steps.
/** Positive numbers, x ≥ 1. Returns {from, to} (inclusive) of a subarray with sum x, or null. O(n). */static int[] subarraySum(int[] a, long x) { int n = a.length, right = 0; // the window is a[left..right-1] long sum = 0; for (int left = 0; left < n; left++) { while (right < n && sum + a[right] <= x) { sum += a[right++]; } if (sum == x) return new int[] {left, right - 1}; // An empty window means a[left] alone is bigger than x: step past it. if (right == left) right++; else sum -= a[left]; } return null;}- window
- just written
- leaves the window
- ruled out
- sum = x
Find a subarray with sum 8. The window runs from L to R. Each turn, R moves right while the sum stays ≤ 8, then L moves one step.
/** Positive numbers, x ≥ 1. Returns {from, to} (inclusive) of a subarray with sum x, or null. O(n). */static int[] subarraySum(int[] a, long x) { int n = a.length, right = 0; // the window is a[left..right-1] long sum = 0; for (int left = 0; left < n; left++) { while (right < n && sum + a[right] <= x) { sum += a[right++]; } if (sum == x) return new int[] {left, right - 1}; // An empty window means a[left] alone is bigger than x: step past it. if (right == left) right++; else sum -= a[left]; } return null;}- L
- 0
- R
- –
- sum
- 0
- x
- 8
- R moves
- 0
2SUM
2SUM: find two values in the array whose sum is x. First sort. Then L starts at the smallest value and R at the largest. On each turn, R moves left as long as a[L] + a[R] > x, and then L moves one step right.
Why is it safe to throw values away? If a[L] + a[R] > x, then a[R] is too big even with the smallest remaining partner, so it can’t be in any pair. If a[L] + a[R] < x, then a[L] is too small even with the largest remaining partner. For [1, 4, 5, 6, 7, 9, 9, 10] and x = 12: 1 + 10 = 11 is too small, so L moves; 4 + 10, 4 + 9 and 4 + 9 are too big, so R moves left three times; 4 + 7 = 11 is too small; and then 5 + 7 = 12.
That’s O(n log n) for the sort plus O(n) for the walk. A binary search for x − a[i] for every i also gives O(n log n).
2SUM: array mein do values dhundho jinka sum x ho. Pehle sort karo. Phir L sabse chhoti value pe aur R sabse badi pe. Har turn mein R tab tak left jaata hai jab tak a[L] + a[R] > x, phir L ek step right.
Values phenkna safe kyun hai? Agar a[L] + a[R] > x, toh a[R] bache hue sabse chhote partner ke saath bhi bada hai — kisi pair mein nahi ho sakta. Agar a[L] + a[R] < x, toh a[L] bache hue sabse bade partner ke saath bhi chhota hai. [1, 4, 5, 6, 7, 9, 9, 10] aur x = 12 pe: 1 + 10 = 11 chhota, toh L hila; 4 + 10, 4 + 9 aur 4 + 9 bade, toh R teen baar left; 4 + 7 = 11 chhota; aur phir 5 + 7 = 12.
Sort ka O(n log n) plus walk ka O(n). Har i ke liye x − a[i] ki binary search bhi O(n log n) deti hai.
/** a is sorted. Returns positions {i, j}, i < j, with a[i] + a[j] = x, or null. O(n) after sorting. */static int[] twoSum(int[] a, long x) { int right = a.length - 1; for (int left = 0; left < right; left++) { while (left < right && (long) a[left] + a[right] > x) { right--; } if (left == right) break; long s = (long) a[left] + a[right]; if (s == x) return new int[] {left, right}; } return null;}- too big: R moves
- too small: L moves
- ruled out
- pair found
The array is sorted. L starts at the smallest value and R at the largest. Each turn, R moves left while a[L] + a[R] > 12; then L moves right.
/** a is sorted. Returns positions {i, j}, i < j, with a[i] + a[j] = x, or null. O(n) after sorting. */static int[] twoSum(int[] a, long x) { int right = a.length - 1; for (int left = 0; left < right; left++) { while (left < right && (long) a[left] + a[right] > x) { right--; } if (left == right) break; long s = (long) a[left] + a[right]; if (s == x) return new int[] {left, right}; } return null;}- L
- 0
- R
- 7
- a[L] + a[R]
- 11
- x
- 12
- pointer moves
- 0
/** 3SUM in O(n²): fix the first value a[i], then run 2SUM on the part to its right. a is sorted. */static int[] threeSum(int[] a, long x) { for (int i = 0; i < a.length; i++) { int left = i + 1, right = a.length - 1; while (left < right) { long s = (long) a[i] + a[left] + a[right]; if (s == x) return new int[] {i, left, right}; if (s < x) left++; else right--; } } return null;}My notesMere notes
8.2Nearest smaller elements
Problem: for every element, find the nearest smaller element before it: the first smaller value you meet walking left. It may not exist.
Go left to right with a stack of positions whose values increase from bottom to top. For each element:
- Pop while the top is ≥ the current element.
- Now the top, if any, is the answer.
- Push the current element.
Why can popped elements be forgotten? Once a smaller (or equal) element appears closer, an older larger element can never be the nearest smaller element for anything that comes later.
For [1, 3, 4, 2, 5, 3, 4, 2] the answers are –, 1, 3, 1, 2, 2, 3, 1. When the 2 arrives, it pops 4 and 3 at once, and at the end the stack holds just 1 and 2.
The amortized argument: one element can pop many others, but every element is pushed once and popped at most once. That’s at most 2n stack operations in total, so O(n).
Problem: har element ke liye uske pehle ka nearest smaller element dhundho — left chalte hue milne wali pehli chhoti value. Ho sakta hai na ho.
Left se right chalo, ek stack ke saath jismein positions hain aur unki values neeche se upar badhti hain. Har element pe:
- Jab tak top ≥ current element, pop karo.
- Ab top (agar hai) hi answer hai.
- Current element push karo.
Pop hue elements bhool kyun sakte hain? Jaise hi koi chhota (ya barabar) element zyada paas aa gaya, purana bada element aage aane wale kisi ka bhi nearest smaller kabhi nahi ban sakta.
[1, 3, 4, 2, 5, 3, 4, 2] ke answers: –, 1, 3, 1, 2, 2, 3, 1. 2 aate hi 4 aur 3 ek saath pop hote hain, aur end mein stack mein sirf 1 aur 2 bachte hain.
Amortized argument: ek element kai doosron ko pop kar sakta hai, par har element ek baar push aur max ek baar pop hota hai. Total max 2n stack operations — yaani O(n).
/** answer[i] = the position of the nearest smaller element before i, or -1 if there is none. */static int[] nearestSmaller(int[] a) { int n = a.length; int[] answer = new int[n]; int[] stack = new int[n]; // positions; their values increase from bottom to top int top = 0; for (int i = 0; i < n; i++) { while (top > 0 && a[stack[top - 1]] >= a[i]) { top--; } answer[i] = top == 0 ? -1 : stack[top - 1]; stack[top++] = i; } return answer;}- current
- on the stack
- popped
- just written
- nearest smaller
For each element, find the nearest smaller element to its left. The stack holds positions whose values increase from bottom to top.
/** answer[i] = the position of the nearest smaller element before i, or -1 if there is none. */static int[] nearestSmaller(int[] a) { int n = a.length; int[] answer = new int[n]; int[] stack = new int[n]; // positions; their values increase from bottom to top int top = 0; for (int i = 0; i < n; i++) { while (top > 0 && a[stack[top - 1]] >= a[i]) { top--; } answer[i] = top == 0 ? -1 : stack[top - 1]; stack[top++] = i; } return answer;}- i
- 0
- pushes
- 0
- pops
- 0
- total ops
- 0
My notesMere notes
8.3Sliding window minimum
A sliding window is a fixed-size subarray of k elements that moves one step right at a time. Problem: report the minimum of every window.
Keep a deque (a queue you can also pop from the back) of positions whose values increase from front to back. Then the front is always the minimum of the current window. When a new element arrives:
- Pop from the back every element ≥ the new one. The new element is smaller and stays in the window longer, so they can never be the minimum again.
- Pop from the front if that position has slid out of the window.
- Push the new element at the back. Once the first window is full, report the front.
For [2, 1, 4, 5, 3, 4, 1, 2] and k = 4, the minimums are 1, 1, 3, 1, 1. Each element enters the deque once and leaves at most once, so this is O(n), whatever k is.
Sliding window k elements ka fixed-size subarray hai jo ek-ek step right khiskta hai. Problem: har window ka minimum batao.
Ek deque (aisi queue jisme back se bhi pop kar sako) rakho, jisme positions hon aur unki values front se back tak badhti hon. Tab front hamesha current window ka minimum hai. Naya element aaye toh:
- Back se pop karo har woh element jo naye se ≥ hai. Naya element chhota hai aur window mein zyada der rahega, toh woh kabhi minimum nahi banenge.
- Front se pop karo agar woh position window se bahar khisak gayi.
- Naya element back pe push karo. Pehli window poori hote hi front report karo.
[2, 1, 4, 5, 3, 4, 1, 2] aur k = 4 ke minimums: 1, 1, 3, 1, 1. Har element deque mein ek baar aata hai aur max ek baar jaata hai — O(n), k kuch bhi ho.
/** mins[i] = the smallest value in the window a[i..i+k-1]. */static int[] windowMins(int[] a, int k) { int n = a.length; int[] mins = new int[n - k + 1]; int[] q = new int[n]; // positions; their values increase from head to tail int head = 0, tail = 0; for (int i = 0; i < n; i++) { while (tail > head && a[q[tail - 1]] >= a[i]) { tail--; } if (tail > head && q[head] <= i - k) { head++; } q[tail++] = i; if (i >= k - 1) { mins[i - k + 1] = a[q[head]]; } } return mins;}- current
- window
- in the deque
- popped
- window minimum
Window size k = 4. The deque holds positions whose values increase from front to back, so its front is always the window minimum.
/** mins[i] = the smallest value in the window a[i..i+k-1]. */static int[] windowMins(int[] a, int k) { int n = a.length; int[] mins = new int[n - k + 1]; int[] q = new int[n]; // positions; their values increase from head to tail int head = 0, tail = 0; for (int i = 0; i < n; i++) { while (tail > head && a[q[tail - 1]] >= a[i]) { tail--; } if (tail > head && q[head] <= i - k) { head++; } q[tail++] = i; if (i >= k - 1) { mins[i - k + 1] = a[q[head]]; } } return mins;}- i
- 0
- k
- 4
- pushes
- 0
- pops
- 0
- total ops
- 0