These are the notes for Java episode 49, the last part of the DSA series. A teacher lines up a class by marks: swapping neighbours (bubble sort) works, but takes seconds for a lakh students, while merge sort (and Arrays.sort) takes milliseconds. Sorted data pays off when searching: binary search finds one roll number among 10 lakh in about 20 steps, as long as every step shrinks the range. Finally, counting the ways up a staircase with plain recursion makes 33 crore calls for 40 steps, and dynamic programming (memoization or a table) cuts that to under a hundred. Every example was run with javac 21.
Timings depend on the machine. The outputs below are real runs; your millisecond numbers will differ.
Sorting
Sorting means putting data in order. Real-life problem: lining up the class by marks.
Bubble sort
Compare neighbours, swap them if they're in the wrong order, and walk the line again and again. Each walk is a pass; after each pass the biggest remaining value has "bubbled" to the end.
import java.util.Arrays;
public class Main {
static void bubbleSort(int[] a) {
for (int pass = 0; pass < a.length - 1; pass++)
for (int i = 0; i < a.length - 1 - pass; i++)
if (a[i] > a[i + 1]) { // neighbours in the wrong order?
int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; // swap them
}
}
public static void main(String[] args) {
int[] marks = {72, 45, 91, 38, 66, 85, 50};
bubbleSort(marks);
System.out.println(Arrays.toString(marks));
}
}
Output:
[38, 45, 50, 66, 72, 85, 91]
1 lakh students
import java.util.Arrays;
public class Main {
static void bubbleSort(int[] a) {
for (int pass = 0; pass < a.length - 1; pass++)
for (int i = 0; i < a.length - 1 - pass; i++)
if (a[i] > a[i + 1]) { int t = a[i]; a[i] = a[i + 1]; a[i + 1] = t; }
}
public static void main(String[] args) {
int n = 100_000; // 1 lakh students
int[] marks = new int[n], copy = new int[n];
for (int i = 0; i < n; i++) marks[i] = copy[i] = (int) ((i * 7919L) % 1000);
long t0 = System.currentTimeMillis();
bubbleSort(marks);
System.out.println("bubble sort: " + (System.currentTimeMillis() - t0) + " ms");
long t1 = System.currentTimeMillis();
Arrays.sort(copy); // Java's built-in sort
System.out.println("Arrays.sort: " + (System.currentTimeMillis() - t1) + " ms");
}
}
Output (one run):
bubble sort: 6657 ms
Arrays.sort: 23 ms
Bubble sort's two nested loops make about n²/2 comparisons: O(n²). Arrays.sort is O(n log n).
Merge sort
Real-life example: two teachers, two sorted piles.
| Sorting answer sheets | Merge sort |
|---|---|
| split the pile in half, give each half to a helper | divide: mid = (lo + hi) / 2 |
| each helper splits again, down to single sheets | recursion (episode 12): one sheet is already sorted |
| merge two sorted piles: always take the smaller top sheet | merge: one pass, O(n) |
| a lakh sheets can only be halved about 17 times | n work × log n levels = O(n log n) |
public class Main {
static void mergeSort(int[] a, int lo, int hi) { // sorts a[lo..hi)
if (hi - lo < 2) return; // 0 or 1 item: already sorted
int mid = (lo + hi) / 2;
mergeSort(a, lo, mid); // sort the left half
mergeSort(a, mid, hi); // sort the right half
int[] out = new int[hi - lo];
int i = lo, j = mid, k = 0;
while (i < mid && j < hi) out[k++] = a[i] <= a[j] ? a[i++] : a[j++]; // take the smaller
while (i < mid) out[k++] = a[i++];
while (j < hi) out[k++] = a[j++];
System.arraycopy(out, 0, a, lo, out.length);
}
public static void main(String[] args) {
int[] marks = {72, 45, 91, 38, 66, 85, 50};
mergeSort(marks, 0, marks.length);
System.out.println(java.util.Arrays.toString(marks));
}
}
Output:
[38, 45, 50, 66, 72, 85, 91]
mergeSort(a, lo, hi)sortsa[lo..hi):loincluded,hiexcluded.- The merge takes the smaller front value with
a[i] <= a[j] ? a[i++] : a[j++]; using<=keeps equal values in their original order, which makes merge sort stable. - Merge sort needs O(n) extra space for the
outarrays. - In real code, call
Arrays.sort: a tuned dual-pivot quicksort for primitive arrays, and TimSort (a merge-sort variant, stable) for objects andCollections.sort.
| Algorithm | Time (worst) | Extra space | Stable |
|---|---|---|---|
| bubble sort | O(n²) | O(1) | yes |
| selection sort | O(n²) | O(1) | no |
| insertion sort | O(n²), O(n) if nearly sorted | O(1) | yes |
| merge sort | O(n log n) | O(n) | yes |
| quicksort | O(n log n) on average, O(n²) worst | O(log n) | no |
Binary search
Real-life problem: finding one roll number in a thick register. Page by page is linear search, O(n). Opening the middle and keeping only the half that can contain the number is binary search: each step halves the range, O(log n). It only works on sorted data.
public class Main {
public static void main(String[] args) {
int n = 1_000_000;
int[] rolls = new int[n];
for (int i = 0; i < n; i++) rolls[i] = 2 * i + 1; // sorted roll numbers
int want = 1_999_999; // the very last one
int linear = 0;
for (int r : rolls) { linear++; if (r == want) break; }
int lo = 0, hi = n - 1, binary = 0;
while (lo <= hi) {
binary++;
int mid = lo + (hi - lo) / 2; // the middle page
if (rolls[mid] == want) break;
if (rolls[mid] < want) lo = mid + 1; // throw away the left half
else hi = mid - 1; // throw away the right half
}
System.out.println("linear search: " + linear + " steps\nbinary search: " + binary + " steps");
}
}
Output:
linear search: 1000000 steps
binary search: 20 steps
loandhimark the part of the array still in play.mid = lo + (hi - lo) / 2gives the same middle as(lo + hi) / 2but can't overflow whenlo + hiis bigger thanInteger.MAX_VALUE.- 2²⁰ ≈ 10 lakh, so 20 steps; 100 crore items would need only about 30.
- Built in:
Arrays.binarySearch(array, key)andCollections.binarySearch(list, key)return the index, or a negative number if the key is missing.
The lo = mid bug
public class Main {
static int find(int[] a, int want) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == want) return mid;
if (a[mid] < want) lo = mid; // forgot the + 1
else hi = mid - 1;
}
return -1;
}
public static void main(String[] args) {
int[] rolls = {11, 23, 35, 47, 59};
System.out.println("47 is at index " + find(rolls, 47));
System.out.println("50 is at index " + find(rolls, 50));
}
}
Output: 47 is at index 3, then nothing until Time Limit Exceeded.
Searching for 50: lo = 3, hi = 4, mid = 3, 47 < 50, so lo = mid = 3: nothing changes, forever. Every step must shrink the range: lo = mid + 1, hi = mid - 1.
Dynamic programming
Real-life problem: ways up the ghat steps, taking 1 or 2 steps at a time. The last move came from step n − 1 or from step n − 2, so ways(n) = ways(n - 1) + ways(n - 2), with ways(0) = ways(1) = 1.
Plain recursion
public class Main {
static long calls = 0;
static long ways(int n) { // ways to climb n steps, 1 or 2 at a time
calls++;
if (n <= 1) return 1;
return ways(n - 1) + ways(n - 2); // last move was 1 step, or 2 steps
}
public static void main(String[] args) {
for (int n : new int[]{5, 30, 40}) {
calls = 0;
long w = ways(n);
System.out.println(n + " steps: " + w + " ways, " + calls + " calls");
}
}
}
Output (takes a moment for 40):
5 steps: 8 ways, 15 calls
30 steps: 1346269 ways, 2692537 calls
40 steps: 165580141 ways, 331160281 calls
40 steps: 33 crore calls. ways(40) calls ways(39) and ways(38); ways(39) calls ways(38) again, and so on: the same sub-problems are solved again and again. The number of calls roughly multiplies by 1.6 for every extra step: exponential time, about O(2ⁿ).
Real-life example: write the answer down once.
| In a maths exam | Dynamic programming |
|---|---|
| write each answer in the margin the first time | memoization: store each result (top-down) |
| needed again? look it up | a cache hit, O(1) |
| or fill a table from step 0 upwards | tabulation: fill dp[i] from smaller cells (bottom-up) |
Dynamic programming (DP) solves a problem by breaking it into overlapping sub-problems and solving each one only once. It applies when the best answer is built from answers to smaller sub-problems (optimal substructure).
Memoization (top-down)
public class Main {
static long calls = 0;
static long[] memo = new long[100]; // memo[n] = answer for n steps, 0 = not yet
static long ways(int n) {
calls++;
if (n <= 1) return 1;
if (memo[n] != 0) return memo[n]; // solved before: just look it up
return memo[n] = ways(n - 1) + ways(n - 2);
}
public static void main(String[] args) {
for (int n : new int[]{5, 30, 40, 90}) {
calls = 0;
memo = new long[100]; // a fresh notebook each time
long w = ways(n);
System.out.println(n + " steps: " + w + " ways, " + calls + " calls");
}
}
}
Output:
5 steps: 8 ways, 9 calls
30 steps: 1346269 ways, 59 calls
40 steps: 165580141 ways, 79 calls
90 steps: 4660046610375530309 ways, 179 calls
79 calls instead of 33 crore: each n is computed once, O(n) time, O(n) space. return memo[n] = ... stores the value and returns it in one step. Zero means "not solved yet", which works here because every real answer is at least 1.
Tabulation (bottom-up)
public class Main {
public static void main(String[] args) {
int n = 90;
long[] dp = new long[n + 1]; // dp[i] = ways to reach step i
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2]; // fill the table from the bottom up
System.out.println("90 steps: " + dp[n] + " ways");
}
}
Output:
90 steps: 4660046610375530309 ways
No recursion at all, so no StackOverflowError for big n. Since each cell only needs the two before it, two variables are enough: O(1) space. (long holds up to about 9.2 × 10¹⁸; ways(91) would still fit, ways(92) would overflow.)
Today's Big-O, side by side
| Before | After |
|---|---|
| bubble sort O(n²) | merge sort / Arrays.sort O(n log n) |
| linear search O(n) | binary search O(log n), on sorted data |
| plain recursion O(2ⁿ) | DP O(n) |
Common mistakes (and what you see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| bubble sort on 1 lakh items | no error: seconds instead of milliseconds | O(n²) | Arrays.sort |
if (a[mid] < want) lo = mid; |
Time Limit Exceeded | the range stops shrinking | lo = mid + 1 |
| binary search on unsorted data | no error: -1 for values that are there |
halving needs order | sort first |
int mid = (lo + hi) / 2; on huge arrays |
a negative mid, then ArrayIndexOutOfBoundsException |
lo + hi overflows |
lo + (hi - lo) / 2 |
| recursion with overlapping sub-problems | no error: crores of calls | the same work again and again | memo array or dp table |
| deep recursion for big n | java.lang.StackOverflowError |
one frame per call | bottom-up table |
Mini project: the best snacks for the class party
A 0/1 knapsack: each snack has a price and a "joy" score; buy each at most once and get the most joy within Rs 100.
public class Main {
public static void main(String[] args) {
String[] snack = {"samosa", "vada pav", "dhokla", "kachori", "jalebi"};
int[] price = {20, 25, 40, 30, 35};
int[] joy = {30, 35, 50, 40, 45}; // how much the class will enjoy it
int budget = 100;
// best[b] = most joy with budget b, each snack bought at most once (0/1 knapsack)
int[] best = new int[budget + 1];
for (int i = 0; i < snack.length; i++)
for (int b = budget; b >= price[i]; b--) // backwards: each snack used once
best[b] = Math.max(best[b], best[b - price[i]] + joy[i]);
System.out.println("Most joy within Rs " + budget + ": " + best[budget]);
}
}
Output:
Most joy within Rs 100: 130
best[b] is the most joy possible with budget b. Looping the budget backwards makes sure each snack is used at most once. The winning set is dhokla, jalebi and vada pav: Rs 100 for 130 joy. Time O(snacks × budget).
Practice
- Selection sort, and count its swaps.
- Binary search for the first position of a value.
- Steps of 1, 2 or 3: count the ways with DP.
- Coin change: fewest coins for Rs 63 with coins 1, 2, 5, 10, 20.
Solution 1
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] marks = {72, 45, 91, 38, 66, 85, 50};
int swaps = 0;
for (int i = 0; i < marks.length - 1; i++) {
int min = i;
for (int j = i + 1; j < marks.length; j++)
if (marks[j] < marks[min]) min = j; // find the smallest of the rest
if (min != i) {
int t = marks[i]; marks[i] = marks[min]; marks[min] = t;
swaps++;
}
}
System.out.println(Arrays.toString(marks) + " with " + swaps + " swaps");
}
}
Output:
[38, 45, 50, 66, 72, 85, 91] with 3 swaps
Selection sort finds the smallest remaining value and swaps it into place: O(n²) comparisons but at most n − 1 swaps.
Solution 2
public class Main {
static int firstIndex(int[] a, int want) {
int lo = 0, hi = a.length - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] >= want) {
if (a[mid] == want) ans = mid; // a candidate: keep looking left
hi = mid - 1;
} else lo = mid + 1;
}
return ans;
}
public static void main(String[] args) {
int[] marks = {38, 45, 50, 66, 66, 66, 72, 91};
System.out.println("first 66 at index " + firstIndex(marks, 66));
System.out.println("first 70 at index " + firstIndex(marks, 70));
}
}
Output:
first 66 at index 3
first 70 at index -1
When a[mid] equals the value, record it and keep searching the left half.
Solution 3
public class Main {
public static void main(String[] args) {
int n = 10;
long[] dp = new long[n + 1];
dp[0] = 1; // one way to stand still
for (int i = 1; i <= n; i++)
for (int step = 1; step <= 3; step++)
if (i - step >= 0) dp[i] += dp[i - step]; // last move: 1, 2 or 3 steps
System.out.println("10 steps, moves of 1-3: " + dp[n] + " ways");
}
}
Output:
10 steps, moves of 1-3: 274 ways
Solution 4
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] coins = {1, 2, 5, 10, 20};
int amount = 63;
int[] fewest = new int[amount + 1]; // fewest[a] = fewest coins to make a
Arrays.fill(fewest, Integer.MAX_VALUE);
fewest[0] = 0;
for (int a = 1; a <= amount; a++)
for (int c : coins)
if (c <= a && fewest[a - c] != Integer.MAX_VALUE)
fewest[a] = Math.min(fewest[a], fewest[a - c] + 1);
System.out.println("Fewest coins for Rs 63: " + fewest[amount]);
}
}
Output:
Fewest coins for Rs 63: 5
20 + 20 + 20 + 2 + 1. (Taking the biggest coin first happens to work for Indian coins, but not for every coin system: with coins 1, 3, 4 and amount 6, greedy gives 4+1+1 while DP finds 3+3.)
Quick quiz
Ten lakh sorted values. At most how many steps does binary search need?
A. about 10 B. about 20 C. about 1,000 D. about 5,00,000
Answer
B. About 20. Each step halves the range, and 2²⁰ ≈ 10 lakh.
Interview questions
- Why is merge sort O(n log n)? log n levels of halving, and each level does O(n) merging work.
- Merge sort vs quicksort? Merge sort: guaranteed O(n log n), stable, O(n) extra space. Quicksort: in-place and fast on average, O(n²) worst case.
- What is a stable sort? Equal elements keep their original relative order.
- Which sort does Java use? Dual-pivot quicksort for primitive arrays; TimSort for objects.
- Conditions for binary search? Sorted (or monotonic) data with random access.
- How do you avoid overflow when computing mid?
lo + (hi - lo) / 2. - What is dynamic programming? Solving overlapping sub-problems once each and reusing the answers.
- Memoization vs tabulation? Top-down recursion with a cache vs bottom-up loops filling a table.
- How do you spot a DP problem? "Count the ways", "minimum/maximum", choices at each step, and a recursive solution that repeats sub-problems.
Glossary
| Term | Meaning |
|---|---|
| Sorting | putting data in order |
| Pass | one walk through the data |
| Bubble sort | swap out-of-order neighbours, pass after pass; O(n²) |
| Selection sort | repeatedly move the smallest remaining value into place; O(n²) |
| Merge sort | split in half, sort each half, merge; O(n log n) |
| Divide and conquer | solve by splitting into smaller copies of the same problem |
| Merge | combine two sorted lists into one sorted list |
| Stable sort | equal values keep their original order |
| TimSort | the stable merge-based sort Java uses for objects |
| Linear search | check items one by one; O(n) |
| Binary search | halve a sorted range each step; O(log n) |
lo, hi, mid |
the bounds of the range in play, and its middle |
| Integer overflow | a value too big for int, wrapping to negative |
| Sub-problem | a smaller version of the same problem |
| Overlapping sub-problems | the same sub-problem needed many times |
| Optimal substructure | the best answer is built from best answers to sub-problems |
| Exponential time | work that multiplies with each extra step, e.g. O(2ⁿ) |
| Dynamic programming | solve each overlapping sub-problem once and reuse it |
| Memoization | top-down DP: cache results of recursive calls |
| Tabulation | bottom-up DP: fill a table in order |
| Knapsack | choose items with costs and values to maximise value within a budget |
Summary
- Bubble sort is O(n²); merge sort divides, sorts and merges in O(n log n); use
Arrays.sortin real code. - Binary search finds a value in sorted data in O(log n) steps (about 20 for 10 lakh). Every step must shrink the range:
lo = mid + 1,hi = mid - 1. - Recursion that repeats the same sub-problems explodes. Dynamic programming solves each once: memoization (top-down) or tabulation (bottom-up).
- That completes DSA parts 1 to 3: Big-O, two pointers, sliding windows, core data structures, sorting, searching and DP.
- Next episode: the capstone project, a library management system.