These are the notes for Java episode 47, the first of three DSA (data structures and algorithms) episodes. An algorithm is a step-by-step method to solve a problem. Asha has a Rs 500 gift card and wants two items that cost exactly 500: we solve it by trying every pair (brute force), watch it become hopelessly slow when the shop has 10 lakh items, learn to measure that with Big-O notation, and invent two pointers. Then Ravi wants his best run of days at the chai stall: re-adding every window is slow, and the sliding window fixes it. Every example was run with javac 21.
Timings depend on the machine. The outputs below are real runs; your millisecond numbers will differ, the gap between the algorithms will not.
The problem: spend the gift card exactly
Pair sum: given prices sorted from cheapest to costliest and a target (the card), find two prices that add up to the target.
Brute force: try every pair
public class Main {
public static void main(String[] args) {
int[] prices = {40, 60, 120, 150, 200, 260, 300, 350}; // sorted
int card = 500; // gift card
for (int i = 0; i < prices.length; i++)
for (int j = i + 1; j < prices.length; j++)
if (prices[i] + prices[j] == card) {
System.out.println("Rs " + prices[i] + " + Rs " + prices[j] + " = Rs " + card);
return;
}
System.out.println("No pair found");
}
}
Output:
Rs 150 + Rs 350 = Rs 500
The outer loop picks the first item i, the inner loop tries every item after it, j. Trying every possibility is called brute force. It's correct and easy to explain: always a good first answer in an interview.
10 lakh items: it never finishes
public class Main {
public static void main(String[] args) {
int n = 1_000_000; // 10 lakh items
int[] p = new int[n];
for (int i = 0; i < n; i++) p[i] = 2 * i;
int card = 3;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (p[i] + p[j] == card) { System.out.println("found"); return; }
System.out.println("No pair found");
}
}
Output: nothing. The online compiler stops it with Time Limit Exceeded.
Even prices (2 * i) can never add up to an odd card (3), so this is the worst case: every pair is checked. The code is correct, just far too slow.
Counting the work
public class Main {
static long pairs(int[] p, int card) {
long checks = 0;
for (int i = 0; i < p.length; i++)
for (int j = i + 1; j < p.length; j++) {
checks++;
if (p[i] + p[j] == card) return checks;
}
return checks;
}
public static void main(String[] args) {
for (int n = 10_000; n <= 40_000; n *= 2) {
int[] p = new int[n];
for (int i = 0; i < n; i++) p[i] = 2 * i; // even prices, sorted
long checks = pairs(p, 3); // odd card: no pair, worst case
System.out.println("n = " + n + " checks = " + checks);
}
}
}
Output:
n = 10000 checks = 49995000
n = 20000 checks = 199990000
n = 40000 checks = 799980000
| n (items) | pairs checked | growth |
|---|---|---|
| 10,000 | about 5 crore | |
| 20,000 | about 20 crore | ×4 |
| 40,000 | about 80 crore | ×4 |
| 10,00,000 | about 5,00,000 crore (500 billion) |
With n items there are n × (n − 1) / 2 pairs. Doubling n makes the work four times bigger.
Big-O notation
Big-O describes how the number of steps grows as the input size n grows, not the time in seconds. It usually describes the worst case and ignores constants (n/2 and 3n are both O(n)), because only the growth matters when n is huge.
| Big-O | Name | Example | n = 10 lakh |
|---|---|---|---|
| O(1) | constant | prices[5]: arrays jump straight to an index |
1 step |
| O(log n) | logarithmic | binary search (episode 49) | about 20 steps |
| O(n) | linear | find the maximum; two pointers; sliding window | 10 lakh steps |
| O(n log n) | linearithmic | good sorting (Arrays.sort) |
about 2 crore steps |
| O(n²) | quadratic | nested loops over all pairs | 10 lakh × 10 lakh |
Rules of thumb: a loop over n is O(n); a loop inside a loop, both over n, is O(n²); a loop whose inner part is a constant (say 5 steps) is still O(n).
Two pointers
Real-life example: two fingers on a sorted price list.
| At the shelf | In Java |
|---|---|
| left finger on the cheapest, right finger on the costliest | left = 0, right = n - 1 |
| total too small: swap the cheap item for a costlier one | sum < card → left++ |
| total too big: swap the costly item for a cheaper one | sum > card → right-- |
| fingers meet: no pair | each item looked at once: O(n) |
Why is it safe to move left up when the sum is too small? The right item is already the costliest left in play, so the left item can't reach the target with anything: we can throw it away for good. Each step throws one item away.
public class Main {
static void find(int[] p, int card) {
int left = 0, right = p.length - 1;
while (left < right) {
int sum = p[left] + p[right];
System.out.println(" " + p[left] + " + " + p[right] + " = " + sum);
if (sum == card) {
System.out.println("Found: Rs " + p[left] + " + Rs " + p[right]);
return;
}
if (sum < card) left++; // too little: move the cheap finger up
else right--; // too much: move the costly finger down
}
System.out.println("No pair found");
}
public static void main(String[] args) {
find(new int[]{40, 60, 120, 150, 200, 260, 300, 350}, 500); // sorted
}
}
Output:
40 + 350 = 390
60 + 350 = 410
120 + 350 = 470
150 + 350 = 500
Found: Rs 150 + Rs 350
10 lakh items, worst case again
public class Main {
public static void main(String[] args) {
int n = 1_000_000;
int[] p = new int[n];
for (int i = 0; i < n; i++) p[i] = 2 * i; // sorted
int card = 3;
int left = 0, right = n - 1;
long checks = 0;
while (left < right) {
checks++;
int sum = p[left] + p[right];
if (sum == card) { System.out.println("found"); return; }
if (sum < card) left++; // need more: cheaper side moves up
else right--; // too much: costlier side moves down
}
System.out.println("No pair found after " + checks + " checks");
}
}
Output:
No pair found after 999999 checks
Under a million checks instead of about 500 billion: O(n) instead of O(n²), same answer.
Two pointers needs sorted data
public class Main {
static void find(int[] p, int card) {
int left = 0, right = p.length - 1;
while (left < right) {
int sum = p[left] + p[right];
if (sum == card) {
System.out.println("Found: Rs " + p[left] + " + Rs " + p[right]);
return;
}
if (sum < card) left++; // too little: move the cheap finger up
else right--; // too much: move the costly finger down
}
System.out.println("No pair found");
}
public static void main(String[] args) {
find(new int[]{350, 260, 300, 120, 150, 40, 200, 60}, 500); // NOT sorted
}
}
Output:
No pair found
Wrong answer, and no error: 150 + 350 is in the list. Moving left up only raises the sum when the list is sorted. Sort first with Arrays.sort (O(n log n)), or use a HashSet of prices seen so far (O(n) time, O(n) space).
Sliding window
Real-life problem: the best 3 days in a row of chai sales. A run of k consecutive items is a window.
Brute force: re-add every window
public class Main {
public static void main(String[] args) {
int n = 1_000_000, k = 100_000; // 10 lakh minutes, 1 lakh-minute window
long t0 = System.currentTimeMillis();
int[] sales = new int[n];
for (int i = 0; i < n; i++) sales[i] = (i * 37) % 100;
long best = 0;
for (int start = 0; start + k <= n; start++) {
long sum = 0;
for (int d = start; d < start + k; d++) sum += sales[d]; // add k minutes, again
best = Math.max(best, sum);
}
long ms = System.currentTimeMillis() - t0;
System.out.println("Best stretch: Rs " + best + " (" + ms + " ms)");
}
}
Output (one run):
Best stretch: Rs 4950000 (7729 ms)
About 9 lakh windows × 1 lakh additions each: O(n × k). Neighbouring windows share almost all their items, so the same numbers are added again and again.
Real-life example: slide the frame, don't redo the sum.
| On the calendar | In Java |
|---|---|
| a frame over 3 days: add them once | first window sum, k additions |
| slide one day right: a new day enters, an old day leaves | sum += sales[end] - sales[end - k] |
| note the best total as it slides | best = Math.max(best, sum), one pass: O(n) |
public class Main {
public static void main(String[] args) {
int[] sales = {120, 80, 150, 200, 90, 300, 60, 210, 180, 40}; // 10 days of chai sales
int k = 3; // best 3-day stretch
int sum = 0;
for (int d = 0; d < k; d++) sum += sales[d]; // first window
int best = sum, bestStart = 0;
for (int end = k; end < sales.length; end++) {
sum += sales[end] - sales[end - k]; // add new day, drop old day
if (sum > best) { best = sum; bestStart = end - k + 1; }
}
System.out.println("Best 3 days: day " + (bestStart + 1) + " to " + (bestStart + k) + ", Rs " + best);
}
}
Output:
Best 3 days: day 4 to 6, Rs 590
Days 4 to 6: 200 + 90 + 300 = 590.
public class Main {
public static void main(String[] args) {
int n = 1_000_000, k = 100_000; // minutes
long t0 = System.currentTimeMillis();
int[] sales = new int[n];
for (int i = 0; i < n; i++) sales[i] = (i * 37) % 100;
long sum = 0;
for (int d = 0; d < k; d++) sum += sales[d];
long best = sum;
for (int end = k; end < n; end++) {
sum += sales[end] - sales[end - k]; // slide by one minute
best = Math.max(best, sum);
}
long ms = System.currentTimeMillis() - t0;
System.out.println("Best stretch: Rs " + best + " (" + ms + " ms)");
}
}
Output (one run):
Best stretch: Rs 4950000 (10 ms)
Off-by-one
public class Main {
public static void main(String[] args) {
int[] sales = {120, 80, 150, 200, 90, 300, 60, 210, 180, 40};
int k = 3, sum = 0;
for (int d = 0; d < k; d++) sum += sales[d];
int best = sum;
for (int end = k; end <= sales.length; end++) { // <= : one step too far
sum += sales[end] - sales[end - k];
best = Math.max(best, sum);
}
System.out.println("Best: Rs " + best);
}
}
Output:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 10 out of bounds for length 10
at Main.main(Main.java:8)
Valid indexes are 0 to length - 1. An off-by-one error is a loop that runs one time too many or too few: check the first and last index of every loop.
Space complexity
Time complexity is how the steps grow; space complexity is how the extra memory grows, beyond the input.
| Algorithm | Time | Extra space |
|---|---|---|
| brute-force pair sum | O(n²) | O(1) |
| two pointers (sorted) | O(n) | O(1): left, right, sum |
| HashSet pair sum (unsorted) | O(n) | O(n) |
| brute-force window | O(n × k) | O(1) |
| sliding window | O(n) | O(1): sum, best |
In an interview, give both: "O(n) time, O(1) space".
Common mistakes (and what you see)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| nested loops over 10 lakh items | Time Limit Exceeded | O(n²): about 500 billion checks | two pointers, O(n) |
| two pointers on an unsorted array | no error: "No pair found", which is wrong | moving left no longer raises the sum |
Arrays.sort first |
for (int end = k; end <= n; end++) |
java.lang.ArrayIndexOutOfBoundsException: Index 10 out of bounds for length 10 |
last index is n - 1 |
end < n |
| re-adding every window | no error: seconds instead of milliseconds | O(n × k) | sum += new - old |
int sum of huge windows |
no error: a wrong, maybe negative total | overflow past Integer.MAX_VALUE |
long sum |
Mini project: the shortest run that reaches a target
A variable-size sliding window: grow it on the right, and while it's big enough, shrink it from the left.
public class Main {
// shortest run of consecutive days whose sales add up to at least target
static int shortest(int[] sales, int target) {
int best = Integer.MAX_VALUE, sum = 0, start = 0;
for (int end = 0; end < sales.length; end++) {
sum += sales[end]; // grow the window on the right
while (sum >= target) { // big enough: try to shrink it
best = Math.min(best, end - start + 1);
sum -= sales[start++]; // drop the leftmost day
}
}
return best == Integer.MAX_VALUE ? 0 : best;
}
public static void main(String[] args) {
int[] sales = {120, 80, 150, 200, 90, 300, 60, 210, 180, 40};
System.out.println("Shortest run with Rs 500+: " + shortest(sales, 500) + " days");
System.out.println("Shortest run with Rs 2000+: " + shortest(sales, 2000) + " days");
}
}
Output:
Shortest run with Rs 500+: 3 days
Shortest run with Rs 2000+: 0 days
Each day enters the window once and leaves once, so this is still O(n), even with the inner while.
Practice
- Two pointers: is a word a palindrome?
- Remove duplicates from a sorted array in place.
- The best average of any 4 consecutive days.
- Count pairs with sum = target in a sorted array (distinct values).
Solution 1
public class Main {
static boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}
public static void main(String[] args) {
for (String w : new String[]{"malayalam", "racecar", "java", "a"})
System.out.println(w + ": " + isPalindrome(w));
}
}
Output:
malayalam: true
racecar: true
java: false
a: true
O(n) time, O(1) space.
Solution 2
import java.util.Arrays;
public class Main {
static int removeDuplicates(int[] a) {
if (a.length == 0) return 0;
int write = 1; // a[0..write) holds the unique values
for (int read = 1; read < a.length; read++)
if (a[read] != a[write - 1]) a[write++] = a[read];
return write;
}
public static void main(String[] args) {
int[] prices = {10, 10, 20, 30, 30, 30, 50};
int k = removeDuplicates(prices);
System.out.println(k + " unique: " + Arrays.toString(Arrays.copyOf(prices, k)));
}
}
Output:
4 unique: [10, 20, 30, 50]
Two pointers moving the same way: read scans every item, write marks where the next unique value goes. O(n) time, O(1) space.
Solution 3
public class Main {
public static void main(String[] args) {
int[] sales = {120, 80, 150, 200, 90, 300, 60, 210, 180, 40};
int k = 4, sum = 0;
for (int d = 0; d < k; d++) sum += sales[d];
int best = sum;
for (int end = k; end < sales.length; end++) {
sum += sales[end] - sales[end - k];
best = Math.max(best, sum);
}
System.out.println("Best 4-day average: Rs " + (best / (double) k));
}
}
Output:
Best 4-day average: Rs 187.5
Solution 4
public class Main {
static int countPairs(int[] p, int target) {
int left = 0, right = p.length - 1, count = 0;
while (left < right) {
int sum = p[left] + p[right];
if (sum == target) { count++; left++; right--; } // distinct values: move both
else if (sum < target) left++;
else right--;
}
return count;
}
public static void main(String[] args) {
int[] prices = {40, 60, 120, 150, 200, 260, 300, 350, 380, 440, 460};
System.out.println("Pairs for Rs 500: " + countPairs(prices, 500));
}
}
Output:
Pairs for Rs 500: 5
40+460, 60+440, 120+380, 150+350, 200+300.
Quick quiz
int count = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < 5; j++)
count++;
What is the time complexity? A. O(1) B. O(n) C. O(n²) D. O(5n²)
Answer
B. O(n). The inner loop always runs 5 times, a constant, so it's 5n steps, and Big-O drops constants. It would be O(n²) only if the inner loop also ran up to n.
Interview questions
- What is Big-O notation? A description of how an algorithm's steps (or memory) grow with the input size, usually in the worst case, ignoring constants and smaller terms.
- Why do we drop constants? For large n, growth dominates: an O(n) algorithm beats an O(n²) one eventually, whatever the constants.
- Time vs space complexity? Steps vs extra memory, both as functions of n.
- When can you use two pointers? Sorted arrays (pair sum, three sum), pairs from both ends (palindromes), or two indexes moving the same way (remove duplicates, merge).
- When is a sliding window the right tool? Questions about contiguous runs: "k in a row", "longest/shortest subarray with ...".
- Fixed vs variable window? Fixed: size k, add one, drop one. Variable: grow on the right, shrink from the left while a condition holds.
- Pair sum on an unsorted array in O(n)? A
HashSet: for each price, check whethertarget - pricewas seen. - Why is the variable window O(n) despite a nested loop? Each element is added once and removed once.
Glossary
| Term | Meaning |
|---|---|
| DSA | data structures and algorithms |
| Algorithm | a step-by-step method to solve a problem |
| Brute force | trying every possibility |
| Pair sum | find two values that add up to a target |
| Worst case | the input that makes an algorithm do the most work |
| n | the size of the input |
| Time complexity | how the number of steps grows with n |
| Space complexity | how the extra memory grows with n |
| Big-O | notation for that growth, e.g. O(n), ignoring constants |
| O(1) | constant: the same work for any n |
| O(log n) | logarithmic: the problem halves each step |
| O(n) | linear: one pass over the data |
| O(n log n) | the cost of good sorting |
| O(n²) | quadratic: every pair |
| Two pointers | two indexes that move through the data, e.g. from both ends |
| Sorted | in order, smallest to largest |
| Window | a run of consecutive items |
| Sliding window | moving a window by adding the new item and dropping the old one |
| Off-by-one error | a loop that runs one time too many or too few |
ArrayIndexOutOfBoundsException |
the runtime error for an index outside 0 to length - 1 |
| Overflow | a number too big for its type, wrapping around |
Summary
- Brute force first: correct and simple. Nested loops over all pairs are O(n²) and die on big inputs.
- Big-O measures how work grows with n: O(1) < O(log n) < O(n) < O(n log n) < O(n²). Drop constants; think worst case.
- Two pointers on sorted data finds a pair in O(n), O(1) space. Unsorted data gives wrong answers.
- Sliding window:
sum += new - oldturns O(n × k) into O(n). Watch the last index:n - 1. - Always state time and space complexity.
- Next episode: linked lists, stacks, queues, trees and graphs.