Home/

...

/

Introduction

Introduction

Some learning resources for the Two Pointers pattern

Real-world problems

The following are a few real-world problems that can be solved using the Two Pointers pattern:

Transmission Error

In a network protocol, response packets take the same route (in reverse) back to the source as the request packet did to the destination. Sometimes the path may differ due to errors, and we can tolerate at most one diversion router. The path, in terms of IDs of routers along the way, is recorded in an array present inside the packet. We need to identify the paths with more than one diversion router, so our topology remains intact and transmission errors are detected.

We’ll be provided with an array of integers representing the router IDs. The routers at the start and end of the path will always be the same. The first half of the array will show the request packet’s path from source to destination, while the second half will show the response packet’s path from the destination back to the source. We need to determine whether the same path is followed from source to destination and from destination to source, except for possibly one additional router ID in either the request or response packet’s paths.

The following illustration might clarify this behavior:

Balloon Splash

We have to develop the game named Balloon Splash. Assume that there are multiple colored balloons, and we have to shoot a column of balloons of the same color. We can only splash k consecutive balloons of the same color. Once a set of k consecutive balloons is splashed, any balloons above it will fall to replace them. We will keep shooting until it is not possible to shoot k consecutive balloons of the same color. In the end, there will not be any k consecutive balloons left. For this problem, our input will be in the form of the English alphabet. Each letter will represent a unique colored balloon.

Let’s go through the following illustration to understand this problem:

Dry-run templates

The following is the implementation of the solution provided for the Remove Duplicates (easy) problem:

Press + to interact
Python 3.5
def remove_duplicates(arr):
  # index of the next non-duplicate element
  next_non_duplicate = 1
  i = 0
  while(i < len(arr)):
    if arr[next_non_duplicate - 1] != arr[i]:
      arr[next_non_duplicate] = arr[i]
      next_non_duplicate += 1
    i += 1
  return next_non_duplicate
def main():
  print(remove_duplicates([2,4,4,5,6]))
  #print(remove_duplicates([2, 2, 2, 11]))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

Input array: [2, 4, 4, 5, 6]

Iteration No.

Line No.

next_non_duplicate

i

arr

-

3-4

1

0

[2,4,4,5,6]

1

11

1

1

[2,4,4,5,6]

2

7-9

2

1

[2,4,4,5,6]

2

11

2

2

[2,4,4,5,6]

3

11

2

3

[2,4,4,5,6]

4

7-9

3

3

[2,4,5,5,6]

4

11

3

4

[2,4,5,5,6]

5

7-9

4

4

[2,4,5,6,6]

5

11

4

5

[2,4,5,6,6]

Sample Input #2

Input array: [1, 1, 1, 3, 3, 3]

Iteration No.

Line No.

next_non_duplicate

i

arr

-

3-4

1

0

[1,1,1,3,3,3]

1

11

1

1

[1,1,1,3,3,3]

2

11

1

2

[1,1,1,3,3,3]

3

11

1

3

[1,1,1,3,3,3]

4

7-9

2

3

[1,3,1,3,3,3]

4

11

2

4

[1,3,1,3,3,3]

5

11

2

5

[1,3,1,3,3,3]

6

11

2

6

[1,3,1,3,3,3]

Trace generation

Press + to interact
Python 3.5
def remove_duplicates(arr):
  # index of the next non-duplicate element
  next_non_duplicate = 1
  i = 0 # initialise the scouting pointer
  while(i < len(arr)):
    print("Iteration " + str(i+1))
    if arr[next_non_duplicate - 1] != arr[i]: # a different character has been found
      arr[next_non_duplicate] = arr[i] # copy over the different character to the non-duplicate section of the array
      next_non_duplicate += 1 # move the non-duplicate pointer forward
      print("\t Line 7-9:\ti: " + str(i) + ", next_non_duplicate: " + str(next_non_duplicate) + ", arr: " + str(arr))
      print("\t Line 7-9:\tarr[i]: " + str(arr[i]) + ", arr[next_non_duplicate-1]: " + str(arr[next_non_duplicate-1]) + ", arr: " + str(arr))
    i += 1 # move the scouting pointer forward
    print("\t Line 11:\ti:" + str(i) + ", next_non_duplicate: " + str(next_non_duplicate) + ", arr: " + str(arr))
    if i < len(arr) and next_non_duplicate < len(arr):
      print("\t Line 11:\tarr[i]: " + str(arr[i]) + ", arr[next_non_duplicate-1]: " + str(arr[next_non_duplicate-1]) + ", arr: " + str(arr))    
  return next_non_duplicate
def main():
  i = 0
  arr = [[1,1,1,3,3,3], [2,2,2,11]]
  for i in range(len(arr)):
    print("arr: " + str(arr[i]) + "\n")
    print("\nLength of the array after removing duplicates: " + str(remove_duplicates(arr[i])))
    print(("-"*100) + "\n")
main()