Two Pointer Technique on Arrays in DSA Javascript - Deep Dive

Overview - Two Pointer Technique on Arrays

What is it?

The Two Pointer Technique on Arrays is a way to solve problems by using two markers or pointers that move through the array to find answers efficiently. Instead of checking every element against every other, these pointers help narrow down the search by moving from different ends or positions. This method is especially useful for sorted arrays or when looking for pairs or subarrays with certain properties. It helps reduce the time it takes to solve problems compared to checking all possibilities.

Why it matters

Without the Two Pointer Technique, many array problems would require checking all pairs or combinations, which takes a lot of time and computer power. This technique makes solutions faster and more efficient, saving time and resources. It is widely used in real-world applications like searching, sorting, and optimizing data processing. Without it, programs would run slower and be less practical for large data sets.

Where it fits

Before learning this, you should understand basic arrays and how to loop through them. Knowing sorting and simple searching helps too. After mastering two pointers, you can learn more advanced techniques like sliding window, binary search, and divide and conquer. It fits into the broader study of algorithm optimization and problem-solving strategies.

Mental Model

Core Idea

Use two markers moving through the array to find answers by comparing or combining elements without checking every pair.

Think of it like...

Imagine you and a friend standing at opposite ends of a hallway looking for matching shoes. You both walk towards each other, checking pairs as you go, instead of one person checking every shoe alone.

Array: [1, 3, 5, 7, 9, 11]
Pointers:  ↑                 ↑
           left             right

Process:
- Compare elements at left and right
- Move left pointer right or right pointer left based on condition
- Repeat until pointers meet or condition is met

Build-Up - 7 Steps

1

Foundation

Understanding Array Basics

Concept: Learn what arrays are and how to access elements using indexes.

An array is a list of items stored in order. Each item has a position called an index, starting from 0. You can get or change an item by using its index. For example, in JavaScript, arr[0] gets the first item.

Result

You can read and write any element in the array by its position.

Knowing how to access array elements is essential because two pointers rely on moving through these positions.

2

Foundation

Basic Looping Through Arrays

Concept: Learn how to move through an array using loops to check or process elements.

You can use a for loop to go from the start to the end of an array. For example, for(let i = 0; i < arr.length; i++) { console.log(arr[i]); } prints each element.

Result

You can visit every element in order and perform actions on them.

Understanding loops helps you grasp how pointers move step by step through the array.

3

Intermediate

Introducing Two Pointers Concept

Concept: Use two pointers starting at different positions to scan the array simultaneously.

Instead of one loop, use two variables to mark positions. For example, left = 0 and right = arr.length - 1. Compare arr[left] and arr[right], then move one pointer based on the problem's rule.

Result

You can find pairs or conditions faster by narrowing the search from both ends.

Using two pointers reduces the number of checks needed, making solutions more efficient.

4

Intermediate

Two Pointer Example: Sum to Target

🤔Before reading on: do you think two pointers can find two numbers that add to a target faster than checking all pairs? Commit to yes or no.

Concept: Find two numbers in a sorted array that add up to a target using two pointers.

Start with left at 0 and right at end. Calculate sum = arr[left] + arr[right]. If sum equals target, return the pair. If sum is less, move left pointer right to increase sum. If sum is more, move right pointer left to decrease sum. Repeat until pointers meet.

Result

For arr = [1, 3, 5, 7, 9], target = 12, output: 3 and 9 or 5 and 7.

Knowing how to adjust pointers based on sum helps quickly find pairs without checking all combinations.

5

Intermediate

Two Pointers for Removing Duplicates

Concept: Use two pointers to overwrite duplicates in a sorted array to keep only unique elements.

One pointer (slow) tracks the position to write unique elements. The other (fast) scans through the array. When fast finds a new unique element, copy it to slow's position and move slow forward. This way, duplicates are skipped.

Result

For arr = [1,1,2,2,3], after process: [1,2,3] with length 3.

Two pointers can help modify arrays in place efficiently without extra space.

6

Advanced

Two Pointer Sliding Window Technique

🤔Before reading on: do you think two pointers can also help find subarrays with certain sums or properties? Commit to yes or no.

Concept: Use two pointers to create a moving window over the array to find subarrays matching conditions.

Set both pointers at start. Move right pointer to expand the window and include more elements. If the window's sum or property exceeds the target, move left pointer to shrink the window. Continue adjusting until the condition is met or all subarrays are checked.

Result

Find the smallest subarray with sum >= target or count subarrays with certain properties efficiently.

Two pointers can dynamically adjust the range of elements considered, enabling efficient subarray problems.

7

Expert

Handling Edge Cases and Unsorted Arrays

🤔Before reading on: do you think two pointers always work on unsorted arrays? Commit to yes or no.

Concept: Understand when two pointers work best and how to adapt or avoid them for unsorted arrays or complex conditions.

Two pointers work best on sorted arrays or when order matters. For unsorted arrays, sorting first or using other methods like hash maps might be better. Also, careful pointer movement is needed to avoid infinite loops or missing elements. Sometimes, combining two pointers with other techniques yields the best results.

Result

Knowing limits helps choose the right approach and avoid bugs or inefficiencies.

Recognizing the technique's boundaries prevents misuse and guides combining it with other methods.

Under the Hood

Two pointers are just two variables holding indexes that move through the array based on conditions. Internally, this means accessing array elements by index and updating pointer values. Because arrays allow direct access by index, moving pointers is fast and simple. The technique avoids nested loops by using linear passes, reducing time complexity from quadratic to linear or near-linear.

Why designed this way?

The technique was designed to optimize problems where checking all pairs is too slow. By leveraging sorted order or problem constraints, two pointers reduce unnecessary checks. Alternatives like nested loops are simpler but inefficient. Two pointers strike a balance between simplicity and speed, making them a popular choice in algorithm design.

┌─────────────┐
│   Array     │
│ [1,3,5,7,9] │
└─────┬───────┘
      │
┌─────▼───────┐
│ Pointers    │
│ left -> 0   │
│ right -> 4  │
└─────┬───────┘
      │
┌─────▼───────────────┐
│ Compare arr[left] +  │
│ arr[right]          │
│ Move pointers based  │
│ on sum vs target     │
└─────────────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Do two pointers always require the array to be sorted? Commit to yes or no.

Common Belief: Two pointers only work if the array is sorted.

Reality: While two pointers often work best on sorted arrays, they can be used on unsorted arrays for certain problems like partitioning or rearranging elements.

Why it matters: Believing sorting is always required limits the use of two pointers and misses simpler solutions for unsorted arrays.

Quick: Do two pointers always move towards each other? Commit to yes or no.

Common Belief: Two pointers always start at opposite ends and move towards each other.

Reality: Two pointers can both move forward, or one can stay fixed while the other moves, depending on the problem. They don't always move towards each other.

Why it matters: Assuming fixed movement patterns restricts problem-solving creativity and leads to incorrect implementations.

Quick: Does using two pointers always guarantee the fastest solution? Commit to yes or no.

Common Belief: Two pointers always give the fastest solution for array problems.

Reality: Two pointers improve efficiency in many cases but are not always the fastest. Sometimes hash maps or binary search are better depending on the problem.

Why it matters: Overusing two pointers without considering alternatives can lead to suboptimal solutions.

Expert Zone

1

Two pointers can be combined with sorting to solve complex problems like 3-sum or 4-sum efficiently.

2

Pointer movement decisions often depend on problem constraints; subtle changes can drastically affect correctness and performance.

3

In-place modifications with two pointers save memory but require careful index management to avoid overwriting needed data.

When NOT to use

Avoid two pointers when the array is unsorted and the problem requires random access or when hash-based lookups provide faster solutions. For example, finding pairs with a given sum in an unsorted array is often better solved with a hash map.

Production Patterns

Two pointers are used in real systems for tasks like merging sorted data streams, removing duplicates in-place, and sliding window algorithms for network packet analysis or real-time data processing.

Connections

Sliding Window Technique

Two pointers form the basis of the sliding window method by defining a dynamic range within the array.

Understanding two pointers helps grasp how windows expand and shrink efficiently to solve subarray problems.

Hash Map Usage

Two pointers and hash maps are alternative approaches for problems like finding pairs with a target sum.

Knowing when to use two pointers versus hash maps improves problem-solving flexibility and efficiency.

Human Visual Search

Two pointers mimic how humans scan from two ends to find matches faster than checking every item.

Recognizing this connection shows how algorithms often reflect natural problem-solving strategies.

Common Pitfalls

#1 Moving pointers incorrectly causing infinite loops or missed elements.

Wrong approach:

while (left < right) {
if (arr[left] + arr[right] < target) {
right--;
} else {
left++;
}
}

Correct approach:

while (left < right) {
if (arr[left] + arr[right] < target) {
left++;
} else {
right--;
}
}

Root cause:

Confusing which pointer to move based on the sum condition leads to pointers moving in the wrong direction.

#2 Using two pointers on unsorted arrays without sorting or adapting the approach.

Wrong approach:

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--;
}

Correct approach:

Use a hash map to find pairs in unsorted arrays instead of two pointers:
const seen = new Set();
for (const num of arr) {
if (seen.has(target - num)) return true;
seen.add(num);
}

Root cause:

Assuming two pointers work the same on unsorted arrays without sorting or alternative methods.

#3 Not updating pointers inside the loop causing infinite loops.

Wrong approach:

while (left < right) {
if (arr[left] + arr[right] === target) return true;
// forgot to move pointers here
}

Correct approach:

while (left < right) {
if (arr[left] + arr[right] === target) return true;
else if (arr[left] + arr[right] < target) left++;
else right--;
}

Root cause:

Forgetting to move pointers inside the loop traps the program in an endless cycle.

Key Takeaways

The Two Pointer Technique uses two markers moving through an array to solve problems efficiently by reducing unnecessary checks.

It works best on sorted arrays but can be adapted or combined with other methods for unsorted data.

Understanding how and when to move each pointer is crucial to avoid bugs and achieve optimal performance.

Two pointers form the foundation for more advanced methods like sliding windows and in-place array modifications.

Recognizing the technique's limits and alternatives ensures you choose the best approach for each problem.

Practice

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

easy

A. Use two indices moving towards each other or in the same direction to solve problems efficiently

B. Use two nested loops to compare every pair of elements

C. Sort the array first and then use binary search

D. Use recursion to divide the array into two parts

Solution

1. Step 1: Understand the technique

   The two pointer technique uses two indices (pointers) to traverse the array, often starting from opposite ends or the same end.

2. Step 2: Purpose of two pointers

   This helps solve problems like finding pairs, removing duplicates, or partitioning without extra space and in linear time.

3. Final Answer:

   Use two indices moving towards each other or in the same direction to solve problems efficiently -> Option A

4. Quick Check:

   Two pointers = two indices moving efficiently [OK]

Hint: Think of two fingers scanning array ends or start [OK]

Common Mistakes:

• Confusing with nested loops approach
• Assuming sorting is always required
• Thinking recursion is part of two pointers

2. Which of the following is the correct syntax to initialize two pointers left and right for an array arr in JavaScript?

easy

A. var left = 1, right = arr.length;

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

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

D. const left = 0, right = arr.length - 1;

Solution

1. Step 1: Understand pointer initialization

   For two pointers starting at the array ends, left starts at 0 (start), right at arr.length - 1 (end).

2. Step 2: Check each option

   const left = 0, right = arr.length - 1; correctly sets left = 0 and right = arr.length - 1. Others have incorrect indices.

3. Final Answer:

   const left = 0, right = arr.length - 1; -> Option D

4. Quick Check:

   Start pointer at 0, end pointer at length-1 [OK]

Hint: Start left at 0 and right at last index [OK]

Common Mistakes:

• Setting right pointer to arr.length (out of bounds)
• Swapping left and right initialization
• Using 1-based indexing instead of 0-based

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

const arr = [1, 2, 3, 4, 5];
let left = 0;
let right = arr.length - 1;
const result = [];
while (left <= right) {
  if (arr[left] + arr[right] === 6) {
    result.push([arr[left], arr[right]]);
    left++;
    right--;
  } else if (arr[left] + arr[right] < 6) {
    left++;
  } else {
    right--;
  }
}
console.log(result);

medium

A. [[2,4],[3,3]]

B. [[1,5],[3,3]]

C. [[1,5],[2,4],[3,3]]

D. [[1,5],[2,4]]

Solution

1. Step 1: Trace the two pointers and sums

   Initially left=0 (1), right=4 (5), sum=6 -> push [1,5], move left=1, right=3.
   Now left=1 (2), right=3 (4), sum=6 -> push [2,4], move left=2, right=2.
   Now left=2 (3), right=2 (3), sum=6 -> push [3,3], move left=3, right=1 but loop ends since left > right.

2. Step 2: Check the result array

   Result contains [[1,5],[2,4],[3,3]]. But note the condition left <= right allows the middle element pairing only if left equals right.
   Here, at left=2 and right=2, sum=6, so [3,3] is added.

3. Final Answer:

   [[1,5],[2,4],[3,3]] -> Option C

4. Quick Check:

   Pairs summing to 6 = [[1,5],[2,4],[3,3]] [OK]

Hint: Check sums at left and right, move pointers accordingly [OK]

Common Mistakes:

• Ignoring the case when left equals right
• Not updating pointers correctly after finding a pair
• Assuming only pairs with different indices count

4. Find the bug in the following code that uses two pointers to check if an array is sorted in non-decreasing order.

function isSorted(arr) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    if (arr[left] > arr[left + 1]) {
      return false;
    }
    left++;
  }
  return true;
}

medium

A. The loop condition should be left <= right

B. The right pointer is unused and unnecessary

C. The comparison should be between arr[left] and arr[right]

D. The function does not handle empty arrays

Solution

1. Step 1: Analyze pointer usage

   The variable right is set but never used inside the loop or condition, making it unnecessary.

2. Step 2: Check loop and comparison logic

   The loop correctly checks adjacent elements using left pointer only, so right can be removed without affecting logic.

3. Final Answer:

   The right pointer is unused and unnecessary -> Option B

4. Quick Check:

   Unused variable right pointer = bug [OK]

Hint: Check if all declared variables are used [OK]

Common Mistakes:

• Thinking right pointer must be used in two pointer technique always
• Changing loop condition unnecessarily
• Confusing adjacent element checks with two pointer sum checks

5. Given a sorted array arr and a target sum target, which code snippet correctly uses the two pointer technique to find if there exists a pair that sums to target?

const arr = [1, 3, 4, 5, 7, 10, 12];
const target = 9;
// Which snippet is correct?

hard

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

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

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

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

Solution

1. Step 1: Understand two pointer approach for pair sum

   Start with pointers at array ends: left=0, right=length-1. Move pointers based on sum compared to target.

2. Step 2: Check each option logic

   let left = 0, right = arr.length - 1; while (left < right) { const sum = arr[left] + arr[right]; if (sum === target) return true; else if (sum < target) left++; else right--; } return false; correctly moves left pointer forward if sum < target, right pointer backward if sum > target, and returns true if sum equals target.
   let left = 0, right = arr.length - 1; while (left <= right) { const sum = arr[left] + arr[right]; if (sum === target) return true; else if (sum > target) left++; else right--; } return false; incorrectly moves left pointer forward when sum > target.
   for (let left = 0, right = arr.length - 1; left < right; left++, right--) { if (arr[left] + arr[right] === target) return true; } return false; moves both pointers every iteration, missing some pairs.
   let left = 0, right = 0; while (left < arr.length && right < arr.length) { if (arr[left] + arr[right] === target) return true; else if (arr[left] + arr[right] < target) right++; else left++; } return false; starts both pointers at 0, which is incorrect for this problem.

3. Final Answer:

   Option A code snippet -> Option A

4. Quick Check:

   Correct pointer moves based on sum vs target [OK]

Hint: Move left if sum less, right if sum more [OK]

Common Mistakes:

• Moving wrong pointer when sum is greater or smaller
• Using for loop that moves both pointers simultaneously
• Starting both pointers at same index