Find Subarrays With Equal Sum

Easy
1797.

Find Subarrays With Equal Sum

Find Subarrays With Equal Sum is an easy coding problem on arrays and hash table, asked in Morgan Stanley interviews.

You are given an integer array nums. Decide whether there are two subarrays of length 2 with equal sums that start at different indices.

Return true if such a pair exists and false otherwise. (A subarray is a contiguous, non-empty part of the array; the two subarrays may overlap.)

Example 1

Input
nums = [3,1,2,2]
Output
true
Explanation
`[3,1]` (start 0) and `[2,2]` (start 2) both sum to 4.

Example 2

Input
nums = [1,2,3,4,5]
Output
false
Explanation
The adjacent sums 3, 5, 7 and 9 are all different.

Example 3

Input
nums = [0,0,0]
Output
true
Explanation
`[0,0]` at index 0 and `[0,0]` at index 1 overlap but start at different indices, and both sum to 0.

Constraints

  • 2 <= nums.length <= 1000
  • -10^9 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var findSubarrays = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Subarrays With Equal Sum — Problem & Solution

Find Subarrays With Equal Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find Subarrays With Equal Sum is an easy coding problem on arrays and hash table, asked in Morgan Stanley interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table
  • Asked at: Morgan Stanley
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array nums. Decide whether there are two subarrays of length 2 with equal sums that start at different indices.

Return true if such a pair exists and false otherwise. (A subarray is a contiguous, non-empty part of the array; the two subarrays may overlap.)

Example 1

Input: nums = [3,1,2,2]
Output: true
Explanation: `[3,1]` (start 0) and `[2,2]` (start 2) both sum to 4.

Example 2

Input: nums = [1,2,3,4,5]
Output: false
Explanation: The adjacent sums 3, 5, 7 and 9 are all different.

Example 3

Input: nums = [0,0,0]
Output: true
Explanation: `[0,0]` at index 0 and `[0,0]` at index 1 overlap but start at different indices, and both sum to 0.

Constraints

  • 2 <= nums.length <= 1000
  • -10^9 <= nums[i] <= 10^9

Hints for Find Subarrays With Equal Sum

  1. Hint 1

    A length-2 subarray is identified by its start i; its sum is nums[i] + nums[i + 1].

  2. Hint 2

    The question becomes: do any two of these n - 1 sums coincide?

  3. Hint 3

    Insert each sum into a hash set and report a repeat. The sums can reach ±2·10^9, so hold them in 64 bits.

How to solve Find Subarrays With Equal Sum

There are only n - 1 length-2 subarrays, one per start index. Two with equal sums exist exactly when the list of adjacent sums has a duplicate — a hash-set check.

Approach

  1. For i from 0 to n - 2, compute s = nums[i] + nums[i + 1] in 64-bit arithmetic.
  2. If s is already in the set, return true; otherwise insert it.
  3. Return false after the loop.

Why it works

Distinct start indices give distinct subarrays, so a repeated sum in the sequence is precisely a pair of different subarrays with equal sums, and the set detects the first repeat.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Two values of 10^9 sum past the 32-bit range — use 64-bit sums in typed languages.
  • Overlapping subarrays count ([0,0,0] is true); only the start indices must differ.

Reference solution

Python

from typing import List

def findSubarrays(nums: List[int]) -> bool:
    seen = set()
    for i in range(len(nums) - 1):
        s = nums[i] + nums[i + 1]
        if s in seen:
            return True
        seen.add(s)
    return False

Java

public static boolean findSubarrays(int[] nums) {
    Set<Long> seen = new HashSet<>();
    for (int i = 0; i + 1 < nums.length; i++) {
        if (!seen.add((long) nums[i] + nums[i + 1])) return true;
    }
    return false;
}

C++

bool findSubarrays(vector<int>& nums) {
    unordered_set<long long> seen;
    for (size_t i = 0; i + 1 < nums.size(); i++) {
        if (!seen.insert((long long)nums[i] + nums[i + 1]).second) return true;
    }
    return false;
}

JavaScript

var findSubarrays = function(nums) {
    var seen = new Set();
    for (var i = 0; i + 1 < nums.length; i++) {
        var s = nums[i] + nums[i + 1];
        if (seen.has(s)) return true;
        seen.add(s);
    }
    return false;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets