Longest Subarray With Restricted Pair Sums solution and explanation
6 more videos on this problem
Leetcode Weekly Contest 521 | Q3 - Longest Subarray With Restricted Pair Sums (4067)Kumar K [Amazon] · 45:37 · 691 views
4067. Longest Subarray With Restricted Pair Sums (Leetcode Medium)Programming Live with Larry · 22:42 · 396 views
Leetcode 4067 | Longest Subarray With Restricted Pair Sums | Leetcode weekly contest 521CodeWithMeGuys · 24:41 · 267 views
Longest Subarray With Restricted Pair Sums | Sliding Window | Observation | Leetcode 4067Manjeet Dhayal · 13:36 · 190 views
LeetCode: 4067 | Longest Subarray With Restricted Pair Sums | Java | HindiCode Kage · 18:07 · 187 views
Longest Subarray With Restricted Pair Sums | Leetcode 4067 |Weekly Contest 521 | Dry Run |Time&SpaceVijay Algorithms · 33:42 · 73 views
Q3. Longest Subarray With Restricted Pair Sums | Weekly Contest 521 | LeetCodeaniketdevlp · 16:16
The problem
You are given an integer array nums.
A subarray nums[l..r] is valid if there are no three distinct indices i, j, and k such that l <= i, j, k <= r and:
nums[i] + nums[j] == nums[k]
Return the maximum length of a valid subarray of nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [2,3,5,3,2,1]
Output: 3
Explanation:
Consider the subarray [3, 5, 3]. The pairs of elements at distinct indices have the following sums:
3 + 5 = 83 + 3 = 6, using the two different occurrences of 35 + 3 = 8
None of these sums is an element at the remaining index, so the subarray is valid.
Every subarray of length 4 contains 2, 3, and 5 at distinct indices, where 2 + 3 = 5. Therefore, no longer valid subarray exists, and the answer is 3.
Example 2:
Input: nums = [3,4,5,6]
Output: 4
Explanation:
The sums obtained from every pair of elements at distinct indices are 7, 8, 9, 9, 10, and 11. None of these values appears at the remaining index, so the entire array is valid.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 500
Approach overview
Problem Overview: You are given an array of integers and a forbidden pair sum. Find the length of the longest contiguous subarray in which no two distinct elements add up to the forbidden value. Every window you consider must stay valid, and you want the longest one.
Approach 1: Brute Force Check Every Subarray (O(n^3) time, O(1) space)
Fix a start index, then extend the end index one element at a time. Before adding each new element, scan the current window for a partner that would complete the forbidden sum. If you find one, stop extending from that start. This works on every input and is easy to verify, but the inner scan repeats work you already did for the previous end index. Use it to confirm correctness on small inputs, not as a submission.
Approach 2: Sliding Window with a Hash Set (O(n) time, O(n) space)
Maintain a left and right pointer and a hash table that stores the values currently inside the window. When you move right onto a new value x, compute target - x and check whether it is in the set. If it is, the window is invalid. Shrink from the left, removing values from the set, until that partner is gone. Then add x and update the maximum length. Each element enters and leaves the set at most once, so the total work is linear. The key insight is that you only need membership checks, not pair enumeration, because the forbidden condition is a single lookup against the current window. This is a classic sliding window pattern, and the two-pointer movement is what keeps it linear.
Recommended for interviews: Interviewers expect the sliding window with a hash set. Presenting the brute force first shows you understand the constraint. Moving to the window with O(1) membership checks shows you recognize that the problem reduces to a set lookup, which is the skill they are testing. Mention that a duplicate value can pair with itself when the forbidden sum is twice that value, and handle that case explicitly with a count map instead of a plain set.
If you want more practice with this pattern, work through related problems tagged array problems that use windows over sequences.
Solution
Thinking
n\le 1000. Checking three indices inside every subarray adds another quadratic factor on top of the two endpoints and does not finish in time.Once
a+b=coccurs, every longer interval that contains it is also invalid, so the left end only moves right as the right end moves right. A newly addedxbreaks the window only when it equals the sum of two values already inside, or the difference of two such values.Keep the number of pair sums and absolute differences in the window. If
xhits either count, delete elements from the left and remove the pairs they belong to. Each pair is inserted once and deleted once.
The window nums[l..r] is valid exactly when no three distinct indices have two elements summing to the third. An invalid segment stays invalid in every longer interval that contains it, so the left end only increases as the right end grows.
Let m=max(nums). cntS[s] is the number of pairs in the current window whose values sum to s, and cntD[d] is the number of pairs whose absolute difference is d. Sums are at most 2m and differences are at most m.
The value at the right end is x, and the window before it is added is [l,r). Adding x makes the window invalid exactly when some pair already sums to x, or some pair already differs by x. The first case means x is the sum. The second means x is an addend and the other two elements are still in the window. Every value is positive, so the absolute difference is enough.
While that happens, remove the left element y and subtract the sums and differences of y with each element that remains in [l,r). After the window is valid again, add the sums and differences of x with each element of [l,r), and update the answer with r-l+1.
Each pair is inserted when the later end enters and deleted when the earlier end leaves. The time complexity is O(n^2) and the space complexity is O(m).
class Solution:
def maxSubarray(self, nums: List[int]) -> int:
mx = max(nums)
cnt_s = [0] * (mx << 1 | 1)
cnt_d = [0] * (mx + 1)
ans = l = 0
for r, x in enumerate(nums):
while cnt_s[x] > 0 or cnt_d[x] > 0:
y = nums[l]
l += 1
for z in nums[l:r]:
cnt_s[y + z] -= 1
cnt_d[abs(y - z)] -= 1
for y in nums[l:r]:
cnt_s[x + y] += 1
cnt_d[abs(x - y)] += 1
ans = max(ans, r - l + 1)
return ansclass Solution {
public int maxSubarray(int[] nums) {
int mx = 0;
for (int x : nums) {
mx = Math.max(mx, x);
}
int[] cntS = new int[(mx << 1) | 1];
int[] cntD = new int[mx + 1];
int ans = 0;
int l = 0;
for (int r = 0; r < nums.length; r++) {
int x = nums[r];
while (cntS[x] > 0 || cntD[x] > 0) {
int y = nums[l++];
for (int i = l; i < r; i++) {
int z = nums[i];
cntS[y + z]--;
cntD[Math.abs(y - z)]--;
}
}
for (int i = l; i < r; i++) {
int y = nums[i];
cntS[x + y]++;
cntD[Math.abs(x - y)]++;
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
}class Solution {
public:
int maxSubarray(vector<int>& nums) {
int mx = ranges::max(nums);
vector<int> cntS((mx << 1) | 1);
vector<int> cntD(mx + 1);
int ans = 0;
int l = 0;
for (int r = 0; r < nums.size(); r++) {
int x = nums[r];
while (cntS[x] > 0 || cntD[x] > 0) {
int y = nums[l++];
for (int i = l; i < r; i++) {
int z = nums[i];
cntS[y + z]--;
cntD[abs(y - z)]--;
}
}
for (int i = l; i < r; i++) {
int y = nums[i];
cntS[x + y]++;
cntD[abs(x - y)]++;
}
ans = max(ans, r - l + 1);
}
return ans;
}
};function maxSubarray(nums: number[]): number {
let mx = 0;
for (const x of nums) {
mx = Math.max(mx, x);
}
const cntS = new Array((mx << 1) | 1).fill(0);
const cntD = new Array(mx + 1).fill(0);
let ans = 0;
let l = 0;
for (let r = 0; r < nums.length; r++) {
const x = nums[r];
while (cntS[x] > 0 || cntD[x] > 0) {
const y = nums[l++];
for (let i = l; i < r; i++) {
const z = nums[i];
cntS[y + z]--;
cntD[Math.abs(y - z)]--;
}
}
for (let i = l; i < r; i++) {
const y = nums[i];
cntS[x + y]++;
cntD[Math.abs(x - y)]++;
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}func maxSubarray(nums []int) int {
mx := slices.Max(nums)
cntS := make([]int, (mx<<1)|1)
cntD := make([]int, mx+1)
ans := 0
l := 0
for r, x := range nums {
for cntS[x] > 0 || cntD[x] > 0 {
y := nums[l]
l++
for i := l; i < r; i++ {
z := nums[i]
cntS[y+z]--
d := y - z
if d < 0 {
d = -d
}
cntD[d]--
}
}
for i := l; i < r; i++ {
y := nums[i]
cntS[x+y]++
d := x - y
if d < 0 {
d = -d
}
cntD[d]++
}
ans = max(ans, r-l+1)
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n^3) | O(1) | Small inputs or verifying correctness |
| Sliding Window with Hash Set | O(n) | O(n) | General case and interview solution |
Frequently asked questions
Longest Subarray With Restricted Pair Sums Python solution
In Python, use a set for the window values and two indices, left and right. Loop right over the array, while the complement of nums[right] is in the set, remove nums[left] and increment left. Add nums[right] to the set and set the answer to the maximum of the current answer and right minus left plus one.
Is Longest Subarray With Restricted Pair Sums easy or hard?
It is a medium-level problem with a 37.8 percent acceptance rate. The brute force is straightforward, but getting to linear time requires recognizing that the window only needs fast membership checks and that the left pointer should move only as far as necessary.
How to solve Longest Subarray With Restricted Pair Sums in O(n)?
Keep a hash set of the values in the current window. For each new value x, check whether target minus x is in the set. If it is, move the left pointer forward and remove values from the set until it is not. Then insert x and update the answer with the window length.
What is the best approach for Longest Subarray With Restricted Pair Sums?
The best approach is a sliding window with a hash set. Expand the right pointer, check whether the complement of the new value is already in the window, and shrink from the left until the window is valid again. This runs in O(n) time and O(n) space.
What data structure is used in Longest Subarray With Restricted Pair Sums?
The solution uses a hash set to track values in the current window, giving O(1) average membership checks. A count map can replace the set when the same value may appear more than once in the window.
What is the time complexity of Longest Subarray With Restricted Pair Sums?
The optimal sliding window solution runs in O(n) time because each index enters and leaves the window at most once. The brute force approach that rescans the window for every start and end runs in O(n^3) time.
Is Longest Subarray With Restricted Pair Sums asked at Google, Amazon, or Meta?
Problems tagged with array, hash table, and sliding window appear often in interviews at large tech companies, including Google, Amazon, and Meta. Check the company tags on FleetCode for the latest reported frequency, since company-specific data changes over time.