You are given an integer array nums.
An element nums[i] is considered valid if it satisfies at least one of the following conditions:
The first and last elements are always valid.
Return an array of all valid elements in the same order as they appear in nums.
Example 1:
Input: nums = [1,2,4,2,3,2]
Output: [1,2,4,3,2]
Explanation:
nums[0] and nums[5] are always valid.nums[1] and nums[2] are strictly greater than every element to their left.nums[4] is strictly greater than every element to its right.[1, 2, 4, 3, 2].Example 2:
Input: nums = [5,5,5,5]
Output: [5,5]
Explanation:
[5, 5].Example 3:
Input: nums = [1]
Output: [1]
Explanation:
Since there is only one element, it is always valid. Thus, the answer is [1].
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100Problem Overview: You are given an array of integers and need to count the elements that are greater than every element to their left and smaller than every element to their right. These elements maintain the sorted order if the array were split around them, making them "valid" according to the constraint.
Approach 1: Brute Force Scan (O(n^2) time, O(1) space)
The straightforward approach checks every element individually. For each index i, iterate through all elements on the left to verify that none are greater, and iterate through all elements on the right to confirm none are smaller. If both conditions hold, the element is valid. This method uses nested loops, leading to O(n^2) time and O(1) extra space. It works for small inputs but becomes slow as the array grows.
Approach 2: Prefix Max + Suffix Min Arrays (O(n) time, O(n) space)
A more efficient strategy precomputes constraints using two helper arrays. Build a prefix array where prefixMax[i] stores the maximum value from index 0 to i. Build a suffix array where suffixMin[i] stores the minimum value from index i to the end. An element at index i is valid if arr[i] > prefixMax[i-1] and arr[i] < suffixMin[i+1]. Both arrays are computed in linear passes, and the final scan also runs once, giving O(n) time and O(n) space. This technique is common in array preprocessing problems.
Approach 3: Optimized Prefix Tracking with Suffix Min (O(n) time, O(n) space)
You can simplify the check by precomputing only the suffix minimum values first. Then iterate from left to right while maintaining a running prefix maximum in a variable. For each position i, compare the current value with the tracked prefix maximum and the next suffix minimum. If prefixMax < arr[i] < suffixMin[i+1], the element is valid. This still runs in O(n) time but avoids storing a full prefix array. The logic relies on constant-time comparisons and sequential passes, a pattern often seen in greedy or preprocessing problems.
Recommended for interviews: Start with the brute force explanation to show you understand the definition of a valid element. Then move to the prefix–suffix preprocessing approach. Interviewers typically expect the O(n) solution using prefix maximum and suffix minimum arrays because it demonstrates familiarity with array preprocessing patterns and efficient constraint checking in array problems.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Left and Right Checks | O(n^2) | O(1) | Small arrays or quick prototype to validate logic |
| Prefix Max and Suffix Min Arrays | O(n) | O(n) | General case and most common interview solution |
| Running Prefix Max + Suffix Min | O(n) | O(n) | Cleaner implementation with fewer stored arrays |
Practice Valid Elements in an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor