Two Number Sum Problem Statement

Given an array of integers, return the indices of the two numbers whose sum is equal to a given target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9.

The output should be [0, 1]. 
Because nums[0] + nums[1] = 2 + 7 = 9.

Two Number Sum Problem solution in Java

METHOD 1. Naive approach: Use two for loops

The naive approach is to just use two nested for loops and check if the sum of any two elements in the array is equal to the given target.

Time complexity: O(n^2)

import java.util.HashMap;
import java.util.Scanner;
import java.util.Map;

class TwoSum {

    // Time complexity: O(n^2)
    private static int[] findTwoSum_BruteForce(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        return new int[] {};
    }


    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        int n = keyboard.nextInt();
        int[] nums = new int[n];

        for(int i = 0; i < n; i++) {
            nums[i] = keyboard.nextInt();
        }
        int target = keyboard.nextInt();

        keyboard.close();

        int[] indices = findTwoSum_BruteForce(nums, target);

        if (indices.length == 2) {
            System.out.println(indices[0] + " " + indices[1]);
        } else {
            System.out.println("No solution found!");
        }
    }
}

# Output
$ javac TwoSum.java
$ java TwoSum
4 2 7 11 15
9
0 1

METHOD 2. Use a HashMap (Most efficient)

You can use a HashMap to solve the problem in O(n) time complexity. Here are the steps:

1. Initialize an empty HashMap.
2. Iterate over the elements of the array.
3. For every element in the array –
   • If the element exists in the Map, then check if it’s complement (target - element) also exists in the Map or not. If the complement exists then return the indices of the current element and the complement.
   • Otherwise, put the element in the Map, and move to the next iteration.

Time complexity: O(n)

import java.util.HashMap;
import java.util.Scanner;
import java.util.Map;

class TwoSum {
    
    // Time complexity: O(n)
    private static int[] findTwoSum(int[] nums, int target) {
        Map<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[] { numMap.get(complement), i };
            } else {
                numMap.put(nums[i], i);
            }
        }
        return new int[] {};
    }
}

METHOD 3. Use Sorting along with the two-pointer sliding window approach

There is another approach which works when you need to return the numbers instead of their indexes. Here is how it works:

1. Sort the array.
2. Initialize two variables, one pointing to the beginning of the array (left) and another pointing to the end of the array (right).
3. Loop until left < right, and for each iteration
   • if arr[left] + arr[right] == target, then return the indices.
   • if arr[left] + arr[right] < target, increment the left index.
   • else, decrement the right index.

This approach is called the two-pointer sliding window approach. It is a very common pattern for solving array related problems.

Time complexity: O(n*log(n))

import java.util.Scanner;
import java.util.Arrays;

class TwoSum {

    // Time complexity: O(n*log(n))
    private static int[] findTwoSum_Sorting(int[] nums, int target) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            if(nums[left] + nums[right] == target) {
                return new int[] {nums[left], nums[right]};
            } else if (nums[left] + nums[right] < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[] {};
    }
}

Liked the Article? Share it on Social media!

Three Number Sum Problem Statement

Given an array of integers, find all triplets in the array that sum up to a given target value.

In other words, given an array arr and a target value target, return all triplets a, b, c such that a + b + c = target.

Example:

Input array: [7, 12, 3, 1, 2, -6, 5, -8, 6]
Target sum: 0

Output: [[2, -8, 6], [3, 5, -8], [1, -6, 5]]

Three Number Sum Problem solution in Java

METHOD 1. Naive approach: Use three for loops

The naive approach is to just use three nested for loops and check if the sum of any three elements in the array is equal to the given target.

Time complexity: O(n^3)

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

class ThreeSum {

  // Time complexity: O(n^3)
  private static List<Integer[]> findThreeSum_BruteForce(int[] nums, int target) {
    List<Integer[]> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
      for (int j = i + 1; j < nums.length; j++) {
        for (int k = j + 1; k < nums.length; k++) {
          if (nums[i] + nums[j] + nums[k] == target) {
            result.add(new Integer[] { nums[i], nums[j], nums[k] });
          }
        }
      }
    }
    return result;
  }

  public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);

    int n = keyboard.nextInt();
    int[] nums = new int[n];

    for (int i = 0; i < n; i++) {
      nums[i] = keyboard.nextInt();
    }
    int target = keyboard.nextInt();

    keyboard.close();

    List<Integer[]> result = findThreeSum_Sorting(nums, target);

    for(Integer[] triplets: result) {
      for(int num: triplets) {
        System.out.print(num + " ");
      }
      System.out.println();
    }
  }
}

METHOD 2. Use Sorting along with the two-pointer sliding window approach

Another approach is to first sort the array, then –

• Iterate through each element of the array and for every iteration,
  • Fix the first element (nums[i])
  • Try to find the other two elements whose sum along with nums[i] gives target. This boils down to the two sum problem.

Time complexity: O(n^2)

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

class ThreeSum {

  // Time complexity: O(n^2)
  private static List<Integer[]> findThreeSum_Sorting(int[] nums, int target) {
    List<Integer[]> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
      int left = i + 1;
      int right = nums.length - 1;
      while (left < right) {
        if (nums[i] + nums[left] + nums[right] == target) {
          result.add(new Integer[] { nums[i], nums[left], nums[right] });
          left++;
          right--;
        } else if (nums[i] + nums[left] + nums[right] < target) {
          left++;
        } else {
          right--;
        }
      }
    }
    return result;
  }
}

METHOD 3. Use a Map/Set

Finally, you can also solve the problem using a Map/Set. You just need to iterate through the array, fix the first element, and then try to find the other two elements using the approach similar to the two sum problem.

I’m using a Set in the following solution instead of a Map as used in the two-sum problem because in the two-sum problem, we had to keep track of the index of the elements as well. But In this problem, we just care about the element and not its index.

Time complexity: O(n^2)

import java.util.Set;
import java.util.Scanner;
import java.util.HashSet;

class ThreeSum {

  // Time complexity: O(n^2)
  private static List<Integer[]> findThreeSum(int[] nums, int target) {
    List<Integer[]> result = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
      int currentTarget = target - nums[i];
      Set<Integer> existingNums = new HashSet<>();
      for (int j = i + 1; j < nums.length; j++) {
        if (existingNums.contains(currentTarget - nums[j])) {
          result.add(new Integer[] { nums[i], nums[j], currentTarget - nums[j] });
        } else {
          existingNums.add(nums[j]);
        }
      }
    }
    return result;
  }
}

Liked the Article? Share it on Social media!

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates from the array in-place such that each element appears only once, and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example

Given array [1, 1, 1, 3, 5, 5, 7]

The output should be 4, with the first four elements of the array being [1, 3, 5, 7]

Remove Duplicates from Sorted Array solution in Java

Given that the array is sorted, all the duplicate elements will appear together.

We can solve the problem in O(n) time complexity by using two pointer sliding window pattern. We’ll keep two pointers (indexes) –

• One index i, to iterate over the array, and
• Another index j, to keep track of the number of unique elements found so far. This index will move only when we modify the array in-place to include a new non-duplicate element.

class RemoveDuplicatesSortedArray {

  private static int removeDuplicates(int[] nums) {
    int n = nums.length;

    /*
     * This index will move only when we modify the array in-place to include a new
     * non-duplicate element.
     */
    int j = 0;

    for (int i = 0; i < n; i++) {
      /*
       * If the current element is equal to the next element, then skip the current
       * element because it's a duplicate.
       */
      if (i < n - 1 && nums[i] == nums[i + 1]) {
        continue;
      }

      nums[j++] = nums[i];
    }

    return j;
  }

  public static void main(String[] args) {
    int[] nums = new int[] { 1, 1, 1, 3, 5, 5, 7 };
    int newLength = removeDuplicates(nums);

    System.out.println("Length of array after removing duplicates = " + newLength);

    System.out.print("Array = ");
    for (int i = 0; i < newLength; i++) {
      System.out.print(nums[i] + " ");
    }
    System.out.println();
  }
}

# Output
Length of array after removing duplicates = 4
Array = 1 3 5 7 

Liked the Article? Share it on Social media!

Maximum Contiguous Subarray Sum problem statement

Given an array of integers, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum = 6.

Maximum Contiguous Subarray Sum solution in Java

This problem can be solved using Kadane’s algorithm in O(n) time complexity.

The algorithm iterates over all the elements of the array (nums) and computes the maximum sum ending at every index (maxEndingHere). Here is how maxEndingHere is calculated:

• Initialize maxEndingHere to nums[0]
• Iterate through the array (1..n). For every iteration:
  • If maxEndingHere + nums[i] < nums[i], that means the previous max was negative and therefore we reset maxEndingHere to nums[i].
  • Otherwise, we set maxEndingHere = maxEndingHere + nums[i]
• We also keep a variable maxSoFar which indicates the maximum sum found so far. And, with every iteration, we check if the current max (maxEndingHere) is greater than maxSoFar. If yes, then we update the value of maxSoFar.

Here is the complete solution:

import java.util.Scanner;

class MaximumSubarray {

  private static int findMaxSubarraySum(int[] nums) {
    int n = nums.length;
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];

    for(int i = 1; i < n; i++) {
      if(maxEndingHere + nums[i] < nums[i]) {
        maxEndingHere = nums[i];
      } else {
        maxEndingHere = maxEndingHere + nums[i];
      }

      if(maxEndingHere > maxSoFar) {
        maxSoFar = maxEndingHere;
      }
    }
    return maxSoFar;
  }

  public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);
    int n = keyboard.nextInt();
    int[] nums = new int[n];
    for(int i = 0; i < n; i++) {
      nums[i] = keyboard.nextInt();
    }

    System.out.println(findMaxSubarraySum(nums));
  }
}

# Output
$ javac MaximumSubarray.java
$ java MaximumSubarray
9 -2 1 -3 4 -1 2 1 -5 4
6

Maximum Contiguous Subarray with Indices

It’s also possible to find out the start and end indices of the maximum contiguous subarray. Here is a modification of the above program which does that and prints the subarray –

import java.util.Scanner;

class MaximumSubarray {

  private static int[] findMaxSubarrayIndices(int[] nums) {
    int n = nums.length;
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];
    int currentStart = 0, maxStart = 0, maxEnd = 0;

    for(int i = 1; i < n; i++) {
      if(maxEndingHere + nums[i] < nums[i]) {
        maxEndingHere = nums[i];
        currentStart = i;
      } else {
        maxEndingHere = maxEndingHere + nums[i];
      }

      if(maxEndingHere > maxSoFar) {
        maxSoFar = maxEndingHere;
        maxStart = currentStart;
        maxEnd = i;
      }
    }

    return new int[]{maxStart, maxEnd};
  }

  public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);
    int n = keyboard.nextInt();
    int[] nums = new int[n];
    for(int i = 0; i < n; i++) {
      nums[i] = keyboard.nextInt();
    }

    int[] indices = findMaxSubarrayIndices(nums);
    int sum = 0;
    System.out.print("Max contiguous subarray: ");
    for(int i = indices[0]; i <= indices[1]; i++) {
      System.out.print(nums[i] + " ");
      sum += nums[i];
    }
    System.out.println();
    System.out.println("Max contiguous subarray sum: " + sum);
  }
}

# Output
$ javac MaximumSubarray.java
$ java MaximumSubarray
9 -2 1 -3 4 -1 2 1 -5 4
Max contiguous subarray: 4 -1 2 1
Max contiguous subarray sum: 6

Given two non-empty arrays of integers, find the pair of values (one value from each array) with the smallest (non-negative) difference.

Example

Input: [1, 3, 15, 11, 2], [23, 127, 235, 19, 8]

Output: [11, 8]; this pair has the smallest difference.

Solution 1. Brute Force approach: Use two for loops

The naive way to solve this problem is to use two for loops and compare the difference of every pair to find the pair with the smallest difference:

Time complexity: O(n^2)

import java.util.Arrays;

class SmallestDifference {

  public static int[] findSmallestDifferencePair_Naive(int[] a1, int[] a2) {
    double smallestDiff = Double.MAX_VALUE;
    int[] smallestDiffPair = new int[2];

    for(int i = 0; i < a1.length; i++) {
      for(int j = 0; j < a2.length; j++) {
        int currentDiff = Math.abs(a1[i] - a2[j]);
        if(currentDiff < smallestDiff) {
          smallestDiff = currentDiff;
          smallestDiffPair[0] = a1[i];
          smallestDiffPair[1] = a2[j];  
        }
      }
    }
    return smallestDiffPair;
  }

  public static void main(String[] args) {
    int[] a1 = new int[] {-1, 5, 10, 20, 28, 3};
    int[] a2 = new int[] {26, 134, 135, 15, 17};

    int[] pair = findSmallestDifferencePair_Naive(a1, a2);
    System.out.println(pair[0] + " " + pair[1]);
  }
}

Solution 2. Use Sorting along with the two-pointer sliding window approach

You can improve upon the brute force solution by first sorting the array and then using the two-pointer sliding window pattern.

Here is how it will work in this case:

• Initialize a variable to keep track of the smallest difference found so far (smallestDiff).
• Sort both the arrays
• Initialize two indexes (one for each array): i = 0 and j = 0.
• Loop until we reach the end of any of the arrays.
• For every iteration:
  • Compare the smallestDiff with abs(a1[i] - a2[j]) and reset it if the new difference is smaller.
  • If a1[i] < a2[j], increment i.
  • Otherwise, increment j

Time complexity: O(mlog(m) + nlog(n))

import java.util.Arrays;

class SmallestDifference {
  public static int[] findSmallestDifferencePair(int[] a1, int[] a2) {
    Arrays.sort(a1);
    Arrays.sort(a2);

    double smallestDiff = Double.MAX_VALUE;
    int[] smallestDiffPair = new int[2];
    int i = 0, j = 0;

    while(i < a1.length && j < a2.length) {
      double currentDiff = Math.abs(a1[i] - a2[j]);
      if(currentDiff < smallestDiff) {
        smallestDiff = currentDiff;
        smallestDiffPair[0] = a1[i];
        smallestDiffPair[1] = a2[j];
      }
      if(a1[i] < a2[j]) {
        i++;
      } else {
        j++;
      }
    }
    return smallestDiffPair;
  }

  public static void main(String[] args) {
    int[] a1 = new int[] {-1, 5, 10, 20, 28, 3};
    int[] a2 = new int[] {26, 134, 135, 15, 17};

    int[] pair = findSmallestDifferencePair(a1, a2);
    System.out.println(pair[0] + " " + pair[1]);
  }
}

Liked the Article? Share it on Social media!