Why Two Pointer Technique Beats Brute Force in DSA Java - Why It Works

Concept Flow - Why Two Pointer Technique Beats Brute Force

Start with two pointers

↓

Pointer1 at start

↓

Check condition between pointers

Yes No↓

Move pointers inward

↓

Repeat check until pointers meet

Two pointers start at opposite ends and move inward based on conditions, reducing repeated work compared to brute force.

Execution Sample

DSA Java

int left = 0, right = arr.length - 1;
while (left < right) {
  if (arr[left] + arr[right] == target) return true;
  else if (arr[left] + arr[right] < target) left++;
  else right--;
}
return false;

This code uses two pointers to find if two numbers sum to a target, moving pointers inward to avoid checking all pairs.

Execution Table

Step	Operation	Pointer Positions	Sum Checked	Action	Visual State
1	Initialize pointers	left=0, right=5	N/A	Start	[3, 5, 7, 10, 12, 15]
2	Check sum	left=0, right=5	3 + 15 = 18	18 > 17, move right--	[3, 5, 7, 10, 12, 15]
3	Check sum	left=0, right=4	3 + 12 = 15	15 < 17, move left++	[3, 5, 7, 10, 12, 15]
4	Check sum	left=1, right=4	5 + 12 = 17	Found target sum, return true	[3, 5, 7, 10, 12, 15]
5	End	N/A	N/A	Stop	[3, 5, 7, 10, 12, 15]

💡 Pointers met or target sum found, loop ends early without checking all pairs.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
left	0	0	1	1	1
right	5	4	4	4	4
sum	N/A	18	15	17	17
found	false	false	false	true	true

Key Moments - 3 Insights

Why do we move the right pointer left when the sum is greater than the target?

Because the array is sorted, decreasing the right pointer reduces the sum, as shown in step 2 of the execution_table.

Why does the loop stop early instead of checking all pairs?

The loop stops when pointers meet or the target sum is found, avoiding unnecessary checks as seen in step 4.

Why is this method faster than brute force?

It avoids checking every pair by moving pointers inward based on sum comparison, reducing time from O(n^2) to O(n), demonstrated by fewer steps in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'sum' at Step 3?

A 18

B 17

C 15

D N/A

💡 Hint

Check the 'Sum Checked' column at Step 3 in the execution_table.

At which step does the algorithm find the target sum?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Action' column for when it says 'Found target sum' in the execution_table.

If the array was not sorted, how would the two pointer technique's efficiency change?

A It would become O(n^2) like brute force

B It would be faster than O(n)

C It would still be O(n)

D It would not work at all

💡 Hint

Two pointer technique relies on sorted arrays to decide pointer moves, see concept_flow.

Concept Snapshot

Two Pointer Technique:
- Use two pointers at array ends
- Move pointers inward based on sum comparison
- Stops early when target found or pointers meet
- Runs in O(n) time on sorted arrays
- Beats brute force O(n^2) by avoiding all pairs

Full Transcript

The two pointer technique uses two pointers starting at opposite ends of a sorted array. At each step, it checks the sum of elements at these pointers. If the sum equals the target, it stops early. If the sum is less than the target, it moves the left pointer right to increase the sum. If the sum is greater, it moves the right pointer left to decrease the sum. This approach reduces the number of checks from all pairs in brute force to a linear number of steps, making it faster and more efficient. The execution table shows how pointers move and sums are checked step-by-step until the target is found or pointers meet.

Practice

1. What is the main advantage of the two pointer technique over brute force in array problems?

easy

A. It uses more memory to store intermediate results

B. It reduces time complexity by avoiding nested loops

C. It always sorts the array first

D. It requires recursion to work

Solution

1. Step 1: Understand brute force approach

   Brute force often uses nested loops, leading to O(n²) time complexity.

2. Step 2: Analyze two pointer technique

   Two pointers move through the array in a single pass, reducing time complexity to O(n).

3. Final Answer:

   It reduces time complexity by avoiding nested loops -> Option B

4. Quick Check:

   Two pointer = faster than brute force [OK]

Hint: Two pointers scan array once, avoiding double loops [OK]

Common Mistakes:

• Thinking two pointer always sorts array
• Assuming it uses more memory
• Believing recursion is required

2. Which of the following is the correct syntax to initialize two pointers in Java for an array arr?

easy

A. int left = arr.length, right = 0;

B. int left = 1, right = arr.length;

C. int left = 0, right = arr.length - 1;

D. int left = -1, right = arr.length + 1;

Solution

1. Step 1: Identify valid pointer positions

   Array indices start at 0 and end at length-1.

2. Step 2: Check initialization correctness

   Left pointer at 0 and right pointer at arr.length - 1 are valid.

3. Final Answer:

   int left = 0, right = arr.length - 1; -> Option C

4. Quick Check:

   Pointers start at array ends [OK]

Hint: Pointers start at 0 and last index (length-1) [OK]

Common Mistakes:

• Starting right pointer at arr.length (out of bounds)
• Starting left pointer at 1 (skips first element)
• Using negative or invalid indices

3. What will be the output of the following Java code snippet?

int[] arr = {1, 2, 3, 4, 5};
int left = 0, right = arr.length - 1;
int sum = 0;
while (left < right) {
  sum += arr[left] + arr[right];
  left++;
  right--;
}
System.out.println(sum);

medium

A. 10

B. 25

C. 15

D. 12

Solution

1. Step 1: Trace pointer movements and sums

   Pairs added: (1+5)=6, (2+4)=6; loop stops when left=right=2.

2. Step 2: Calculate total sum

   Sum = 6 + 6 = 12; loop ends before adding middle element 3.

3. Step 3: Check if middle element added

   Middle element 3 is not added because left == right stops loop.

4. Final Answer:

   12 -> Option D

5. Quick Check:

   Sum pairs from ends = 12 [OK]

Hint: Sum pairs while left < right, middle element excluded [OK]

Common Mistakes:

• Adding middle element when left == right
• Summing all elements instead of pairs
• Miscounting loop iterations

4. Identify the bug in the following two pointer code that tries to find if a pair sums to 10:

int[] arr = {1, 3, 5, 7, 9};
int left = 0, right = arr.length - 1;
boolean found = false;
while (left <= right) {
  int sum = arr[left] + arr[right];
  if (sum == 10) {
    found = true;
    break;
  } else if (sum < 10) {
    left++;
  } else {
    right++;
  }
}
System.out.println(found);

medium

A. Right pointer should decrement, not increment, when sum > 10

B. Left pointer should decrement when sum < 10

C. Loop condition should be left < right, not left <= right

D. Sum calculation is incorrect

Solution

1. Step 1: Understand pointer movement logic

   If sum is less than target, move left pointer right to increase sum; if sum is greater, move right pointer left to decrease sum.

2. Step 2: Identify incorrect pointer update

   Code incorrectly increments right pointer when sum > 10; it should decrement right pointer.

3. Final Answer:

   Right pointer should decrement, not increment, when sum > 10 -> Option A

4. Quick Check:

   Decrease right pointer when sum too big [OK]

Hint: Decrease right pointer if sum too large, increase left if too small [OK]

Common Mistakes:

• Incrementing right pointer instead of decrementing
• Using wrong loop condition
• Miscalculating sum

5. Given a sorted array arr of integers, how can the two pointer technique be used to find all unique pairs that sum to a target value k efficiently?

hard

A. Use two pointers at start and end, move inward adjusting pointers based on sum compared to k

B. Use nested loops to check every pair for sum equal to k

C. Sort the array first, then use binary search for each element to find complement

D. Use recursion to generate all pairs and check sums

Solution

1. Step 1: Initialize two pointers

   Set one pointer at start (left) and one at end (right) of the sorted array.

2. Step 2: Move pointers based on sum comparison

   Calculate sum of elements at pointers; if sum equals k, record pair and move both pointers; if sum less than k, move left pointer right; if sum greater than k, move right pointer left.

3. Step 3: Avoid duplicates by skipping equal elements

   After finding a pair, skip over duplicate elements to ensure unique pairs.

4. Final Answer:

   Use two pointers at start and end, move inward adjusting pointers based on sum compared to k -> Option A

5. Quick Check:

   Two pointer moves inward to find pairs efficiently [OK]

Hint: Move pointers inward based on sum vs target to find pairs fast [OK]

Common Mistakes:

• Using nested loops causing O(n²) time
• Not skipping duplicates leading to repeated pairs
• Using binary search unnecessarily increasing complexity