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
Hint 1
A length-2 subarray is identified by its start
i; its sum isnums[i] + nums[i + 1].Hint 2
The question becomes: do any two of these
n - 1sums coincide?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
- For
ifrom 0 ton - 2, computes = nums[i] + nums[i + 1]in 64-bit arithmetic. - If
sis already in the set, return true; otherwise insert it. - 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 FalseJava
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