Jobs

Interviews

Discussions

Find Subarrays With Equal Sum

Easy

Morgan Stanley

3 views

Topics:

ArraysTwo PointersSliding Windows

Given a 0-indexed integer array nums, determine whether there exist two subarrays of length 2 with equal sum. Note that the two subarrays must begin at different indices.

Return true if these subarrays exist, and false otherwise.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [4,2,4]
Output: true
Explanation: The subarrays with elements [4,2] and [2,4] have the same sum of 6.

Example 2:

Input: nums = [1,2,3,4,5]
Output: false
Explanation: No two subarrays of size 2 have the same sum.

Example 3:

Input: nums = [0,0,0]
Output: true
Explanation: The subarrays [nums[0],nums[1]] and [nums[1],nums[2]] have the same sum of 0. 
Note that even though the subarrays have the same content, the two subarrays are considered different because they are in different positions in the original array.

Constraints:

2 <= nums.length <= 1000
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Find Subarrays With Equal Sum

Easy

Morgan Stanley

3 views

Topics:

ArraysTwo PointersSliding Windows

Given a 0-indexed integer array nums, determine whether there exist two subarrays of length 2 with equal sum. Note that the two subarrays must begin at different indices.

Return true if these subarrays exist, and false otherwise.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [4,2,4]
Output: true
Explanation: The subarrays with elements [4,2] and [2,4] have the same sum of 6.

Example 2:

Input: nums = [1,2,3,4,5]
Output: false
Explanation: No two subarrays of size 2 have the same sum.

Example 3:

Input: nums = [0,0,0]
Output: true
Explanation: The subarrays [nums[0],nums[1]] and [nums[1],nums[2]] have the same sum of 0. 
Note that even though the subarrays have the same content, the two subarrays are considered different because they are in different positions in the original array.

Constraints:

2 <= nums.length <= 1000
-10⁹ <= nums[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the `nums` array? Could they be negative, zero, or very large?
What is the maximum possible length of the `nums` array? This will help me consider space complexity.
If there are multiple pairs of subarrays with the same sum, can I return `true` as soon as I find one, or do I need to find all of them?
If the input array has fewer than 3 elements, should I return `false` or is there a different expectation?
Are there any constraints on the types of numbers allowed, for example, should I only expect integers or would floats be a possibility?

Brute Force Solution

Approach

The brute force method for this problem involves checking every possible pair of groups within the numbers we're given. We essentially try out every combination to see if any two groups have the same total. Think of it like trying out all possible teams and comparing their scores.

Here's how the algorithm would work step-by-step:

First, pick a starting point in your list of numbers.
Then, create a group of numbers by including the next number, then the next, and so on until you reach the end of the list.
Calculate the sum of the numbers in this first group.
Next, start again from a potentially different point in the list and do the same thing: create another group by including numbers one by one until the end of the list is reached.
Calculate the sum of the numbers in this second group.
Compare the sums of the first and second group. If they are equal, you've found a solution!
Keep repeating this process, creating all possible first groups and second groups, comparing their sums each time until you have exhausted every possible combination.

Code Implementation

def find_subarrays_with_equal_sum(number_list):
    list_length = len(number_list)
    for first_subarray_start in range(list_length):
        for first_subarray_end in range(first_subarray_start, list_length):
            first_subarray_sum = 0
            for index in range(first_subarray_start, first_subarray_end + 1):
                first_subarray_sum += number_list[index]

            # Start iterating for the second subarray.
            for second_subarray_start in range(list_length):
                for second_subarray_end in range(second_subarray_start, list_length):

                    # Avoid overlapping subarrays.
                    if first_subarray_end < second_subarray_start or second_subarray_end < first_subarray_start:
                        second_subarray_sum = 0
                        for index in range(second_subarray_start, second_subarray_end + 1):
                            second_subarray_sum += number_list[index]

                        # Found a match!
                        if first_subarray_sum == second_subarray_sum:
                            return True

    # No matching subarrays found.
    return False

Big(O) Analysis

Time Complexity

O(n^3) – The described brute force approach iterates through all possible pairs of subarrays. The outer loop determines the start of the first subarray, giving us n possibilities. The inner loop expands the first subarray, summing elements, up to n elements. Then we have another nested loop starting the second subarray, giving n possibilities. The innermost loop expands the second subarray, summing elements, up to n elements. This results in O(n * n * n) time complexity, or O(n^3).

Space Complexity

O(1) – The provided brute force algorithm calculates sums of subarrays on the fly without storing them in any auxiliary data structures. It only utilizes a few constant-size variables like loop counters or temporary sum storage to compute and compare the sums. The space required does not scale with the input size N (the number of elements in the input list). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The fastest way to find if two equal-sum subarrays exist is to check for duplicate sums. If we encounter the same subarray sum twice while going through the numbers, it means we found two subarrays that add up to the same total. This avoids unnecessary checks.

Here's how the algorithm would work step-by-step:

Start with a sum of zero and a way to remember the sums you have seen.
Go through the list of numbers one by one, each time adding the current number to the running sum.
After adding each number, check if the current sum is already in your memory.
If you find the current sum in your memory, it means that the numbers between the previous time you saw this sum and now form a subarray that adds up to the same amount as a previous one. You're done - you have found two subarrays with the same sum.
If you go through all the numbers and never find a sum that you have already seen before, it means there are no two subarrays with equal sums.

Code Implementation

def find_subarrays_with_equal_sum(numbers) -> bool:
    seen_sums = set()
    current_sum = 0

    for number in numbers:
        current_sum += number

        # If the current sum has already been seen,
        # it indicates a duplicate subarray sum.
        if current_sum in seen_sums:
            return True

        # Store the current sum to check for duplicates later.
        seen_sums.add(current_sum)

    # If no duplicate subarray sums are found,
    # then no two subarrays have equal sums.
    return False

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n once. In each iteration, it performs a constant-time operation which is adding the current element to the running sum and checking if the current sum exists in a hash set. Since hash set lookups take O(1) time on average, the overall time complexity is driven by the single loop, resulting in O(n) time complexity.

Space Complexity

O(N) – The algorithm uses a data structure, described as "a way to remember the sums you have seen", to store the cumulative sums encountered while iterating through the input array. In the worst-case scenario, where all the cumulative sums are distinct, this data structure (likely a hash set or similar) will store N sums, where N is the number of elements in the input array. Therefore, the auxiliary space required grows linearly with the input size, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately, as no subarrays of length 2 can exist.
Input array with only one element	Return false because a subarray of length 2 cannot be formed.
Input array with exactly two elements and they are equal	Calculate sum once, compare only with itself which should return false as indices must differ.
Array with a large number of elements containing duplicates	The hash set approach ensures efficient checking regardless of duplicate presence, scaling linearly with array size.
Array containing only negative numbers	The algorithm handles negative numbers correctly as the sum comparison will work regardless of sign.
Array containing zero(s)	The algorithm handles zeros correctly as the sum comparison will work regardless of value.
Array with integer overflow potential when summing two elements	Use a long data type to store the sum to prevent integer overflow, ensuring accurate comparison.
No two subarrays of length two have the same sum	The algorithm correctly returns false after iterating through the entire array and finding no matching sums in different positions.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the `nums` array? Could they be negative, zero, or very large?
What is the maximum possible length of the `nums` array? This will help me consider space complexity.
If there are multiple pairs of subarrays with the same sum, can I return `true` as soon as I find one, or do I need to find all of them?
If the input array has fewer than 3 elements, should I return `false` or is there a different expectation?
Are there any constraints on the types of numbers allowed, for example, should I only expect integers or would floats be a possibility?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, pick a starting point in your list of numbers.
Then, create a group of numbers by including the next number, then the next, and so on until you reach the end of the list.
Calculate the sum of the numbers in this first group.
Next, start again from a potentially different point in the list and do the same thing: create another group by including numbers one by one until the end of the list is reached.
Calculate the sum of the numbers in this second group.
Compare the sums of the first and second group. If they are equal, you've found a solution!
Keep repeating this process, creating all possible first groups and second groups, comparing their sums each time until you have exhausted every possible combination.

Code Implementation

def find_subarrays_with_equal_sum(number_list):
    list_length = len(number_list)
    for first_subarray_start in range(list_length):
        for first_subarray_end in range(first_subarray_start, list_length):
            first_subarray_sum = 0
            for index in range(first_subarray_start, first_subarray_end + 1):
                first_subarray_sum += number_list[index]

            # Start iterating for the second subarray.
            for second_subarray_start in range(list_length):
                for second_subarray_end in range(second_subarray_start, list_length):

                    # Avoid overlapping subarrays.
                    if first_subarray_end < second_subarray_start or second_subarray_end < first_subarray_start:
                        second_subarray_sum = 0
                        for index in range(second_subarray_start, second_subarray_end + 1):
                            second_subarray_sum += number_list[index]

                        # Found a match!
                        if first_subarray_sum == second_subarray_sum:
                            return True

    # No matching subarrays found.
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with a sum of zero and a way to remember the sums you have seen.
Go through the list of numbers one by one, each time adding the current number to the running sum.
After adding each number, check if the current sum is already in your memory.
If you find the current sum in your memory, it means that the numbers between the previous time you saw this sum and now form a subarray that adds up to the same amount as a previous one. You're done - you have found two subarrays with the same sum.
If you go through all the numbers and never find a sum that you have already seen before, it means there are no two subarrays with equal sums.

Code Implementation

def find_subarrays_with_equal_sum(numbers) -> bool:
    seen_sums = set()
    current_sum = 0

    for number in numbers:
        current_sum += number

        # If the current sum has already been seen,
        # it indicates a duplicate subarray sum.
        if current_sum in seen_sums:
            return True

        # Store the current sum to check for duplicates later.
        seen_sums.add(current_sum)

    # If no duplicate subarray sums are found,
    # then no two subarrays have equal sums.
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return false immediately, as no subarrays of length 2 can exist.
Input array with only one element	Return false because a subarray of length 2 cannot be formed.
Input array with exactly two elements and they are equal	Calculate sum once, compare only with itself which should return false as indices must differ.
Array with a large number of elements containing duplicates	The hash set approach ensures efficient checking regardless of duplicate presence, scaling linearly with array size.
Array containing only negative numbers	The algorithm handles negative numbers correctly as the sum comparison will work regardless of sign.
Array containing zero(s)	The algorithm handles zeros correctly as the sum comparison will work regardless of value.
Array with integer overflow potential when summing two elements	Use a long data type to store the sum to prevent integer overflow, ensuring accurate comparison.
No two subarrays of length two have the same sum	The algorithm correctly returns false after iterating through the entire array and finding no matching sums in different positions.