Teaching Kids Programming – Two Pointer Algorithm to Solve Four Sum Problem

Teaching Kids Programming: Videos on Data Structures and Algorithms

A few days ago, we learned to solve the four sum problem using the Bruteforce Algorithm or Depth First Search Algorithm: Teaching Kids Programming – Sum of Four Numbers using Depth First Search Algorithm

Given a list of integers nums and an integer k, return whether there are four distinct elements in the list that add up to k.

Constraints
n ≤ 100 where n is length of nums.
Example 1
Input
nums = [10, 3, 5, 9, 4, 0]
k = 17
Output
True
Explanation
We can use [10, 3, 4, 0] to get 17

Example 2
Input
nums = [2]
k = 8
Output
False
Explanation
There’s no 4 numbers that sum up to 2.

Example 3
Input
nums = [2, 2, 2, 2]
k = 8
Output
True

Hint: Find 2 elements sum up to k

We can use the Two Pointer (Two Sum) on the last two numbers when we have bruteforce the first two numbers.

Four Sum via Two Pointers

We need to first sort the numbers and this takes O(NLogN) time. And then we can bruteforce the first two numbers and apply the two pointer (like Two Sum) algorithm on the right of the second numbers. This takes O(N^3) time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def solve(self, nums, k):
        nums.sort()   # O(NLogN)
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                a, b = j + 1, n - 1
                while a < b:
                    x = nums[i] + nums[j] + nums[a] + nums[b]
                    if x > k:
                        b -= 1
                    elif x == k:
                        return True
                    else:
                        a += 1
        return False c

class Solution:
    def solve(self, nums, k):
        nums.sort()   # O(NLogN)
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                a, b = j + 1, n - 1
                while a < b:
                    x = nums[i] + nums[j] + nums[a] + nums[b]
                    if x > k:
                        b -= 1
                    elif x == k:
                        return True
                    else:
                        a += 1
        return False c

If the sum of current chosen four numbers is smaller than the target, we move the left pointer (third number) to the right, and if it is larger than the target, we need to move the right pointer (fourth number) to the left – until both pointers meet.

Generally speaking, K-sum problems (K is larger or than equal to two), we can bruteforce the K-2 numbers in time – and then apply the Two Pointer which takes O(N) time. Overall, the time complexity is time.

Two sum algorithm’s complexity is O(NLogN) because the sorting dominates.

Two Sum Variation Problems

• Teaching Kids Programming - Two Sum in Binary Search Tree via Inorder and Two Pointer Algorithm
• Teaching Kids Programming - Count Pairs Whose Sum is Less than Target (Two Pointer Algorithm)
• Teaching Kids Programming - Sum of Two Numbers Less Than Target using Two Pointer Algorithm
• Teaching Kids Programming - Two Pointer Algorithm to Solve Four Sum Problem
• Teaching Kids Programming - Recursive Algorithm to Find the Sum of Two Numbers in BSTs
• Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target
• Recursive and Two Pointer Algorithms to Determine Four Sum
• Algorithms to Check Sum of Two Numbers in Binary Search Trees
• Teaching Kids Programming - 3 Different Approaches to Solve Two-Sum Problem
• How to Design a Two-Sum Data Structure?
• How to Find the Closest Sum of Three in an Array using Two Pointer Algorithm? (3Sum Closest)
• Teaching Kids Programming - Three Sum Algorithm
• Teaching Kids Programming – Two Sum Algorithm when Input Array is Sorted
• Teaching Kids Programming – Two Sum Algorithm
• Two Pointer Algorithm to Find Maximum Two Sum Less Than K
• The Two Sum Algorithm using HashMap in C++/Java

–EOF (The Ultimate Computing & Technology Blog) —