We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Subarrays With Equal Sum

Number: 2480

Difficulty: Easy

Paid? No

Companies: Morgan Stanley

Problem Description

Given a 0-indexed integer array, determine whether there exist two subarrays of length 2 with equal sum. Note that the subarrays must start at different indices. Return true if such subarrays exist; otherwise, return false.

Key Insights

  • Only subarrays of length 2 need to be examined.
  • Compute the sum of each adjacent pair in one pass.
  • Use a hash set to track sums that have been seen previously.
  • If a sum repeats, it means there exists another subarray with the same sum.

Space and Time Complexity

Time Complexity: O(n) - Only one pass through the array is needed. Space Complexity: O(n) - In the worst-case, all computed sums are stored in the hash set.

Solution

The problem can be solved by iterating through the array and calculating the sum of each pair of consecutive elements. A hash set is used to store these sums. For each computed sum, check if it already exists in the set. If it does, return true immediately, as this indicates there are two different subarrays (one starting at the current index and another from a previous index) with the same sum. If no matching sum is found after processing all pairs, return false.

Code Solutions

# Python solution with detailed comments
def find_subarrays(nums):
    # Initialize an empty set to store the sums of subarrays of length 2
    seen_sums = set()
    
    # Iterate over the list until the second last element
    for i in range(len(nums) - 1):
        # Calculate the sum of the current subarray of length 2
        current_sum = nums[i] + nums[i+1]
        
        # If the sum has been seen before, return True as duplicate sum exists
        if current_sum in seen_sums:
            return True
        
        # Add the current sum to the set
        seen_sums.add(current_sum)
    
    # If no duplicate subarray sum is found, return False
    return False

# Example usage:
print(find_subarrays([4, 2, 4]))  # Output: True
← Back to All Questions