Two Pointer Technique on Arrays in DSA Typescript - Execution Trace

Concept Flow - Two Pointer Technique on Arrays

Initialize left pointer at start

↓

Initialize right pointer at end

↓

Check condition with left and right pointers

Yes No↓

Process elements

↓

Move pointers inward

↩Back to Check condition

Start with two pointers at opposite ends of the array, check conditions, process elements, then move pointers inward until they meet or cross.

Execution Sample

DSA Typescript

const arr = [1, 3, 5, 7, 9];
let left = 0;
let right = arr.length - 1;
while (left < right) {
  console.log(arr[left], arr[right]);
  left++;
  right--;
}

Print pairs of elements from the start and end moving towards the center using two pointers.

Execution Table

Step	Operation	Left Pointer	Right Pointer	Elements Printed	Pointer Movement	Visual State
1	Initialize pointers	0	4	None	None	[1, 3, 5, 7, 9]
2	Check left < right	0	4	None	None	[1, 3, 5, 7, 9]
3	Print arr[left], arr[right]	0	4	1, 9	None	[1, 3, 5, 7, 9]
4	Move left pointer right	1	4	None	left++	[1, 3, 5, 7, 9]
5	Move right pointer left	1	3	None	right--	[1, 3, 5, 7, 9]
6	Check left < right	1	3	None	None	[1, 3, 5, 7, 9]
7	Print arr[left], arr[right]	1	3	3, 7	None	[1, 3, 5, 7, 9]
8	Move left pointer right	2	3	None	left++	[1, 3, 5, 7, 9]
9	Move right pointer left	2	2	None	right--	[1, 3, 5, 7, 9]
10	Check left < right	2	2	None	None	[1, 3, 5, 7, 9]

💡 Pointers met at index 2, condition left < right is false, loop ends.

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 8	After Step 9	Final
left	0	1	1	2	2	2
right	4	4	3	3	2	2

Key Moments - 3 Insights

Why do we check 'left < right' and not 'left <= right'?

Because when left equals right, both pointers point to the same element, and processing it twice is usually unnecessary. The execution_table row 10 shows the loop stops when left equals right.

What happens if the array has an odd number of elements?

The pointers meet at the middle element without crossing. The middle element is not processed twice. In the example, step 10 shows pointers meeting at index 2 (middle element).

Why do we move both pointers after processing elements?

Moving both pointers inward ensures we process pairs from outside towards the center without overlap. The execution_table rows 4,5 and 8,9 show left and right pointers moving after printing.

Visual Quiz - 3 Questions

Look at the execution_table, what elements are printed at step 7?

A 5 and 5

B 1 and 9

C 3 and 7

D 7 and 3

💡 Hint

Check the 'Elements Printed' column at step 7 in the execution_table.

At which step do the pointers meet and stop the loop?

A Step 10

B Step 9

C Step 8

D Step 6

💡 Hint

Look at the 'Check left < right' condition and its result in the execution_table.

If we change the condition to 'left <= right', what would happen at the end?

A The loop would stop earlier

B The middle element would be printed twice

C The pointers would never meet

D No change in output

💡 Hint

Consider the condition check in step 10 and what happens if it allows left == right.

Concept Snapshot

Two Pointer Technique on Arrays:
- Use two pointers starting at opposite ends.
- Move pointers inward based on condition.
- Process elements at pointers each step.
- Stop when pointers meet or cross.
- Useful for pairwise processing or searching.

Full Transcript

The Two Pointer Technique on Arrays uses two indexes starting at the beginning and end of the array. We check if the left pointer is less than the right pointer. If yes, we process the elements at these pointers, then move the left pointer right and the right pointer left. This repeats until the pointers meet or cross, stopping the loop. This technique helps efficiently process pairs or search in sorted arrays. The example code prints pairs from the outside moving inward. The pointers start at 0 and array length minus one, printing elements at these positions, then moving inward until they meet at the middle. The loop stops when left is no longer less than right, avoiding double processing of the middle element in odd-length arrays.

Practice

1. What is the main idea behind the Two Pointer Technique when used on arrays?

easy

A. Use a single pointer to iterate through the array once

B. Use two indices to scan the array from different ends or positions simultaneously

C. Sort the array before processing it with one pointer

D. Use recursion to divide the array into two parts

Solution

1. Step 1: Understand the technique

   The Two Pointer Technique involves using two indices or pointers to traverse the array, often from opposite ends or different positions.

2. Step 2: Compare with other options

   Options A, C, and D describe different methods like single pointer iteration, sorting, or recursion, which are not the core idea of two pointers.

3. Final Answer:

   Use two indices to scan the array from different ends or positions simultaneously -> Option B

4. Quick Check:

   Two pointers = two indices scanning array [OK]

Hint: Two pointers move independently to cover array efficiently [OK]

Common Mistakes:

• Thinking it uses only one pointer
• Confusing with sorting or recursion
• Assuming pointers move only forward

2. Which of the following is the correct TypeScript syntax to initialize two pointers at the start and end of an array named arr?

easy

A. let left = arr[0], right = arr[arr.length];

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

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

D. let left = arr.length, right = 0;

Solution

1. Step 1: Identify correct pointer initialization

   For two pointers at array ends, left starts at 0 (first index), right at arr.length - 1 (last index).

2. Step 2: Check other options for errors

   let left = 1, right = arr.length; uses invalid indices (arr.length is out of bounds). let left = arr[0], right = arr[arr.length]; assigns values from array elements, not indices. let left = arr.length, right = 0; reverses pointers incorrectly.

3. Final Answer:

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

4. Quick Check:

   Start = 0, End = length-1 [OK]

Hint: Array indices start at 0, last index is length minus one [OK]

Common Mistakes:

• Using arr.length as an index (out of bounds)
• Assigning pointer to array values instead of indices
• Swapping left and right initialization

3. What will be the output of the following TypeScript code?

const arr = [1, 3, 5, 7, 9];
let left = 0;
let right = arr.length - 1;
let sumPairs = [];
while (left < right) {
  sumPairs.push(arr[left] + arr[right]);
  left++;
  right--;
}
console.log(sumPairs);

medium

A. [10, 16]

B. [10, 12]

C. [10, 8]

D. [10, 10]

Solution

1. Step 1: Trace the loop iterations

   Initial pointers: left=0, right=4
   Iteration 1: arr[0]+arr[4] = 1+9=10, sumPairs=[10]
   left=1, right=3
   Iteration 2: arr[1]+arr[3] = 3+7=10, sumPairs=[10,10]
   left=2, right=2 (loop ends as left is not less than right)

2. Step 2: Final output array

   The sumPairs array contains [10, 10] after the loop finishes.

3. Final Answer:

   [10, 10] -> Option D

4. Quick Check:

   Pairs sums = [10, 10] [OK]

Hint: Add elements at left and right, move pointers inward [OK]

Common Mistakes:

• Including middle element sum when left equals right
• Incorrect pointer updates causing infinite loop
• Wrong sum calculations or indices

4. Identify the bug in the following TypeScript code that uses two pointers to find if a sorted array contains two numbers summing to target.

function hasPairSum(arr: number[], target: number): boolean {
  let left = 0;
  let right = arr.length;
  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return true;
    else if (sum < target) left++;
    else right--;
  }
  return false;
}

medium

A. Right pointer initialized to arr.length instead of arr.length - 1

B. Left pointer should start at 1, not 0

C. The loop condition should be left <= right

D. The sum calculation should use arr[left] - arr[right]

Solution

1. Step 1: Check pointer initialization

   The right pointer is set to arr.length, which is out of array bounds. It should be arr.length - 1 to point to the last element.

2. Step 2: Validate other parts

   Left pointer at 0 is correct. Loop condition left < right is standard. Sum calculation uses addition correctly.

3. Final Answer:

   Right pointer initialized to arr.length instead of arr.length - 1 -> Option A

4. Quick Check:

   Right pointer must be last index (length-1) [OK]

Hint: Array last index is length minus one, not length [OK]

Common Mistakes:

• Using arr.length as index causing runtime error
• Changing loop condition incorrectly
• Mistaking sum operation for subtraction

5. Given a sorted array arr of integers, how can you use the Two Pointer Technique to find all unique pairs that sum up to a target value target? Choose the best approach.

hard

A. Initialize two pointers at start and end; move inward adjusting pointers based on sum; skip duplicates to collect unique pairs

B. Use nested loops to check all pairs and add those matching target

C. Sort the array first, then use a hash map to find complements

D. Initialize pointers both at start and move forward checking sums

Solution

1. Step 1: Use two pointers at array ends

   Start with left at 0 and right at arr.length - 1. Calculate sum of elements at these pointers.

2. Step 2: Move pointers and skip duplicates

   If sum equals target, record pair and move both pointers skipping duplicates. If sum less than target, move left pointer right. If sum greater, move right pointer left.

3. Step 3: Collect unique pairs efficiently

   This approach avoids nested loops and handles duplicates by skipping repeated values, ensuring unique pairs.

4. Final Answer:

   Initialize two pointers at start and end; move inward adjusting pointers based on sum; skip duplicates to collect unique pairs -> Option A

5. Quick Check:

   Two pointers + skip duplicates = unique pairs [OK]

Hint: Move pointers inward and skip duplicates for unique pairs [OK]

Common Mistakes:

• Using nested loops causing higher time complexity
• Not skipping duplicates leading to repeated pairs
• Incorrect pointer movement causing missed pairs