Longest Subarray With Restricted Pair Sums - Video Solutions
Leetcode Weekly Contest 521 | Q3 - Longest Subarray With Restricted Pair Sums (4067)
Longest Subarray With Restricted Pair Sums - Video Solution
Watch 7 video solutions for Longest Subarray With Restricted Pair Sums, a medium level problem. This walkthrough by Kumar K [Amazon] has 691 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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