Home/

...

/

Problem Challenge 1

Problem Challenge 1

Dry-run templates

This is the implementation of the solution provided for Problem Challenge 1:

Press + to interact
Python 3.5
def search_quadruplets(arr, target):
  arr.sort()
  quadruplets = []
  for i in range(0, len(arr)-3):
    # skip same element to avoid duplicate quadruplets
    if i > 0 and arr[i] == arr[i - 1]:
      continue
    for j in range(i + 1, len(arr)-2):
      # skip same element to avoid duplicate quadruplets
      if j > i + 1 and arr[j] == arr[j - 1]:
        continue
      search_pairs(arr, target, i, j, quadruplets)
  return quadruplets
def search_pairs(arr, target_sum, first, second, quadruplets):
  left = second + 1
  right = len(arr) - 1
  while (left < right):
    quad_sum = arr[first] + arr[second] + arr[left] + arr[right]
    if quad_sum == target_sum:  # found the quadruplet
      quadruplets.append(
        [arr[first], arr[second], arr[left], arr[right]])
      left += 1
      right -= 1
      while (left < right and arr[left] == arr[left - 1]):
        left += 1  # skip same element to avoid duplicate quadruplets
      while (left < right and arr[right] == arr[right + 1]):
        right -= 1  # skip same element to avoid duplicate quadruplets
    elif quad_sum < target_sum:
      left += 1  # we need a pair with a bigger sum
    else:
      right -= 1  # we need a pair with a smaller sum
def main():
  print(search_quadruplets([4, 1, 2, -1, 1, -3], 1))
  print(search_quadruplets([2, 0, -1, 1, -2, 2], 2))
main()

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

Sample Input #1

Input array: [4, 1, 2, -1, 1, -3] 
Target: 1
Sorted array: [-3, -1, 1, 1, 2, 4]

Iteration No.

Line No.

i

j

left

right

quad_sum

quadruplets

-

3

-

-

-

-

-

[]

1

4

0

-

-

-

-

[]

1

8

0

1

-

-

-

[]

1

17-18

0

1

2

5

-

[]

1

20

0

1

2

5

1

[]

1

22

0

1

2

5

1

[[-3, -1, 1, 4]]

1

19

0

1

4

4

1

[[-3, -1, 1, 4]]

1

8

0

2

-

-

-

[[-3, -1, 1, 4]]

1

17-18

0

2

3

5

-

[[-3, -1, 1, 4]]

1

20

0

2

3

5

3

[[-3, -1, 1, 4]]

1

19

0

2

3

4

3

[[-3, -1, 1, 4]]

1

20

0

2

3

4

1

[[-3, -1, 1, 4]]

1

22

0

2

3

4

1

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

1

19

0

2

4

3

1

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

1

8

0

3

-

-

-

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

2

4

1

-

-

-

-

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

2

8

1

2

-

-

-

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

2

17-18

1

2

3

5

-

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

2

20

1

2

3

5

5

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

2

19

1

2

3

4

-

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

2

20

1

2

3

4

3

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

2

19

1

2

3

3

-

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

2

8

1

3

-

-

-

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

3

4

2

-

-

-

-

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

3

8

2

3

-

-

-

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

3

17-18

2

3

4

5

-

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

3

20

2

3

4

5

8

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

3

19

2

3

4

4

-

[[-3, -1, 1, 4], [-3, 1, 1, 2]]

Sample Input #2

Input array: [2, 0, -1, 1, -2, 2] 
Target: 2
Sorted array: [-2, -1, 0, 1, 2, 2]

Iteration No.

Line No.

i

j

left

right

quad_sum

quadruplets

-

3

-

-

-

-

-

[]

1

4

0

-

-

-

-

[]

1

8

0

1

-

-

-

[]

1

17-18

0

1

2

5

-

[]

1

20

0

1

2

5

-1

[]

1

19

0

1

3

5

-

[]

1

20

0

1

3

5

0

[]

1

19

0

1

4

5

-

[]

1

20

0

1

4

5

1

[]

1

19

0

1

5

5

-

[]

1

8

0

2

-

-

-

[]

1

17-18

0

2

3

5

-

[]

1

20

0

2

3

5

1

[]

1

19

0

2

4

5

-

[]

1

20

0

2

4

5

2

[]

1

22

0

2

4

5

2

[[-2, 0, 2, 2]]

1

19

0

2

5

4

-

[[-2, 0, 2, 2]]

1

8

0

3

-

-

-

[[-2, 0, 2, 2]]

1

17-18

0

3

4

5

-

[[-2, 0, 2, 2]]

1

20

0

3

4

5

3

[[-2, 0, 2, 2]]

1

19

0

3

4

4

-

[[-2, 0, 2, 2]]

2

4

1

-

-

-

-

[[-2, 0, 2, 2]]

2

8

1

2

-

-

-

[[-2, 0, 2, 2]]

2

17-18

1

2

3

5

-

[[-2, 0, 2, 2]]

2

20

1

2

3

5

2

[[-2, 0, 2, 2]]

2

22

1

2

3

5

2

[[-2, 0, 2, 2], [-1, 0, 1, 2]]

2

19

1

2

4

4

-

[[-2, 0, 2, 2], [-1, 0, 1, 2]]

2

8

1

3

-

-

-

[[-2, 0, 2, 2], [-1, 0, 1, 2]]

2

17-18

1

3

4

5

-

[[-2, 0, 2, 2], [-1, 0, 1, 2]]

2

20

1

3

4

5

4

[[-2, 0, 2, 2], [-1, 0, 1, 2]]

2

19

1

3

4

4

-

[[-2, 0, 2, 2], [-1, 0, 1, 2]]

3

4

2

-

-

-

-

[[-2, 0, 2, 2], [-1, 0, 1, 2]]

3

8

2

3

-

-

-

[[-2, 0, 2, 2], [-1, 0, 1, 2]]

3

17-18

2

3

4

5

-

[[-2, 0, 2, 2], [-1, 0, 1, 2]]

3

20

2

3

4

5

5

[[-2, 0, 2, 2], [-1, 0, 1, 2]]

3

19

2

3

4

4

-

[[-2, 0, 2, 2], [-1, 0, 1, 2]]

Step-by-step solution construction

Let’s first write a function search_pairs that can search an array for pairs that match a target sum:

Press + to interact
Python 3.5
def search_pairs_simple(arr, target_sum, start, pairs):
 left = start + 1
 right = len(arr) - 1
 print("\tleft: " + str(left), end=" ")
 print("\tright: " + str(right), end=" ")
  
 while (left < right):
   pair_sum = arr[left] + arr[right]
   print("pair_sum: "+str(pair_sum), end=" ")
   if pair_sum == target_sum:  # found the pair
     pairs.append(
       [arr[left], arr[right]])
     left += 1
     right -= 1
   elif pair_sum < target_sum:
     left += 1  # we need a pair with a bigger sum
   else:
     right -= 1  # we need a pair with a smaller sum
   print("pairs: " + str(pairs), end=" ")
   print("\n\tleft: " + str(left), end = " ")
   print("\tright: " + str(right), end=" ")
 
 
def main():
  arr1 = [2, 0, -1, 1, -2, 2, 1, 1, 1]
  target1 = 2
  pairs = []
  arr1.sort()
  print("arr: " + str(arr1) + " target: " + str(target1))
  search_pairs_simple(arr1, target1, 0, pairs)
main()

We can utilize the above search_pairs method to find the quadruplets we’re looking for. We can set up two outer pointers, i and j, such that i and j iterate through the array in nested loops. Against each pairing of i and j, we can call search_pairs on the remaining array.

The following is the explanation of the code given below:

  1. On lines 5-7, we are starting the iteration with two variables i and j
  2. Here, i moves from 0 to len(arr)-3 and j moves from i+1 to len(arr)-2
  3. We have to find a pair against each i and j, hence we call search_pairs
  4. search_pairs iterates through the remaining array to generate the pairs that fulfil the target sum criterion
  5. On lines 19-22, we compute the sum of the quadruplet and compare it with target
  6. If the sum matches the target, we add the quadruplet to the quadruplets array
  7. Otherwise, we move left and right pointers forward to generate the next pair

Press + to interact
Python 3.5
def search_quadruplets(arr, target):
 arr.sort()
 # print("sorted array: " + str(arr))
 quadruplets = []
 for i in range(0, len(arr)-3):
   print("\ni: " + str(i), end="")
   for j in range(i + 1, len(arr)-2):
     print("\n\tj: " + str(j) + "\tchecking sorted array: " + str(arr))
     search_pairs(arr, target, i, j, quadruplets)
 return quadruplets
 
def search_pairs(arr, target_sum, first, second, quadruplets):
 left = second + 1
 right = len(arr) - 1
 print("\t\tleft: " + str(left), end=" ")
 print("\tright: " + str(right), end=" ")
  
 while (left < right):
   quad_sum = arr[first] + arr[second] + arr[left] + arr[right]
   print("quad_sum: "+str(quad_sum), end=" ")
   if quad_sum == target_sum:  # found the quadruplet
     quadruplets.append(
       [arr[first], arr[second], arr[left], arr[right]])
     left += 1
     right -= 1
   elif quad_sum < target_sum:
     left += 1  # we need a pair with a bigger sum
   else:
     right -= 1  # we need a pair with a smaller sum
   print("quadruplets: " + str(quadruplets), end=" ")
   print("\n\t\tleft: " + str(left), end = " ")
   print("\tright: " + str(right), end=" ")
 
def main():
 arrs = [[2, 0, -1, 1, -2, 2], [4, 1, 1, -1, -1, -3]]
 targets = [2, 5]
 for i in range(len(arrs)):
   print("arr: " + str(arrs[i]) + " target: " + str(targets[i]))
   print("\n\nThe quadruplets that sum to " + str(targets[i]) + " are: " + str(search_quadruplets(arrs[i],targets[i])))
   print(("-"*100) + "\n")
main()

The above code works fine but it generates duplicate quadruplets if there are consecutive duplicate values in the given array. For example, the quadruplets produced for the array [4, 1, 1, -1, -1, -3] with target 5 are [[-1, 1, 1, 4], [-1, 1, 1, 4]]. We need to add conditional statements to skip any duplicate value while iterating the array.

Following is the explanation of the updated code given below:

  1. On line 8, we compare the values iterated by the variable i and continue if the consecutive two indexes have the same value.
  2. On line 13, we compare the values iterated by the variable j and continue if two consecutive indexes have the same value.
  3. On line 34, we compare the value at left and the one just before it. If they are the same, we move left forward. We continue in this manner until we find consecutive, non-duplicate values.
  4. On line 37, we compare the value at right and the one just after it. If they are the same, we move right backwards into the array. Again, we continue doing this until we find consecutive, non-duplicate values.
Press + to interact
Python 3.5
def search_quadruplets(arr, target):
  arr.sort()
  quadruplets = []
  for i in range(0, len(arr)-3):
    print("\ni: " + str(i))
    # skip same element to avoid duplicate quadruplets
    if i > 0 and arr[i] == arr[i - 1]:
      continue
    for j in range(i + 1, len(arr)-2):
      print("\n\tj: " + str(j) + "\tchecking sorted array: " + str(arr))
      # skip same element to avoid duplicate quadruplets
      if j > i + 1 and arr[j] == arr[j - 1]:
        continue
      search_pairs(arr, target, i, j, quadruplets)
  return quadruplets
def search_pairs(arr, target_sum, first, second, quadruplets):
  left = second + 1
  right = len(arr) - 1
  print("\t\tleft: " + str(left), end=" ")
  print("\tright: " + str(right), end=" ")
    
  while (left < right):
    quad_sum = arr[first] + arr[second] + arr[left] + arr[right]
    print("quad_sum: "+str(quad_sum), end=" ")
    if quad_sum == target_sum:  # found the quadruplet
      quadruplets.append(
        [arr[first], arr[second], arr[left], arr[right]])
      left += 1
      right -= 1
      while (left < right and arr[left] == arr[left - 1]):
        left += 1  # skip same element to avoid duplicate quadruplets
      while (left < right and arr[right] == arr[right + 1]):
        right -= 1  # skip same element to avoid duplicate quadruplets
    elif quad_sum < target_sum:
      left += 1  # we need a pair with a bigger sum
    else:
      right -= 1  # we need a pair with a smaller sum
    print("quadruplets: " + str(quadruplets), end=" ")
    print("\n\t\tleft: " + str(left), end = " ")
    print("\tright: " + str(right), end=" ")
def main():
 arrs = [[2, 0, -1, 1, -2, 2], [4, 1, 1, -1, -1, -3]]
 targets = [2, 5]
 for i in range(len(arrs)):
   print("arr: " + str(arrs[i]) + " target: " + str(targets[i]))
   print("\n\nThe quadruplets that sum to " + str(targets[i]) + " are: " + str(search_quadruplets(arrs[i],targets[i])))
   print(("-"*100) + "\n")
main()