Valid Elements in an Array solution and explanation
4 more videos on this problem
Valid Elements in an Array | LeetCode 3912 | Weekly Contest 499 | Java Code | Developer CoderDeveloper Coder · 7:16 · 359 views
LeetCode 3912 | Valid Elements in an Array | Weekly Contest 499 | Prefix & Suffix Max ExplainedAsmita Mhetre · 10:09 · 171 views
3912. Valid Elements in an Array (Leetcode Easy)Programming Live with Larry · 3:21 · 148 views
LeetCode Problem 3912 | Valid Elements in an ArrayRepovive TV · 6:28 · 73 views
LeetCode Weekly Contest 499 | Problem 1 – Valid Elements in an Array | 3912 | Python Solution | EasyAnand Solves · 5:20 · 64 views
The problem
You are given an integer array nums.
An element nums[i] is considered valid if it satisfies at least one of the following conditions:
- It is strictly greater than every element to its left.
- It is strictly greater than every element to its right.
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]andnums[5]are always valid.nums[1]andnums[2]are strictly greater than every element to their left.nums[4]is strictly greater than every element to its right.- Thus, the answer is
[1, 2, 4, 3, 2].
Example 2:
Input: nums = [5,5,5,5]
Output: [5,5]
Explanation:
- The first and last elements are always valid.
- No other elements are strictly greater than all elements to their left or to their right.
- Thus, the answer is
[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] <= 100
Approach overview
Problem 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.
Solution
We can preprocess the array to compute the maximum value to the right of each element and store it in an array right.
Then, we traverse the array from left to right, using a variable left to keep track of the maximum value to the left of the current element. For each element, if it satisfies any of the following conditions, we add it to the answer:
- It is strictly greater than
left. - It is the last element of the array.
- It is strictly greater than
right[i + 1].
During the traversal, we continuously update the value of left.
After the traversal, we return the answer.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the array nums.
class Solution:
def findValidElements(self, nums: list[int]) -> list[int]:
n = len(nums)
right = [nums[-1]] * n
for i in range(n - 2, -1, -1):
right[i] = max(right[i + 1], nums[i])
left = 0
ans = []
for i, x in enumerate(nums):
if x > left or i == n - 1 or x > right[i + 1]:
ans.append(x)
left = max(left, x)
return ansclass Solution {
public List<Integer> findValidElements(int[] nums) {
int n = nums.length;
int[] right = new int[n];
right[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
right[i] = Math.max(right[i + 1], nums[i]);
}
int left = 0;
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
int x = nums[i];
if (x > left || i == n - 1 || x > right[i + 1]) {
ans.add(x);
}
left = Math.max(left, x);
}
return ans;
}
}class Solution {
public:
vector<int> findValidElements(vector<int>& nums) {
int n = nums.size();
vector<int> right(n);
right[n - 1] = nums[n - 1];
for (int i = n - 2; i >= 0; i--) {
right[i] = max(right[i + 1], nums[i]);
}
int left = 0;
vector<int> ans;
for (int i = 0; i < n; i++) {
int x = nums[i];
if (x > left || i == n - 1 || x > right[i + 1]) {
ans.push_back(x);
}
left = max(left, x);
}
return ans;
}
};function findValidElements(nums: number[]): number[] {
const n = nums.length;
const right = new Array(n);
right[n - 1] = nums[n - 1];
for (let i = n - 2; i >= 0; i--) {
right[i] = Math.max(right[i + 1], nums[i]);
}
let left = 0;
const ans: number[] = [];
for (let i = 0; i < n; i++) {
const x = nums[i];
if (x > left || i === n - 1 || x > right[i + 1]) {
ans.push(x);
}
left = Math.max(left, x);
}
return ans;
}func findValidElements(nums []int) []int {
n := len(nums)
right := make([]int, n)
right[n-1] = nums[n-1]
for i := n - 2; i >= 0; i-- {
right[i] = max(right[i+1], nums[i])
}
left := 0
ans := []int{}
for i, x := range nums {
if x > left || i == n-1 || x > right[i+1] {
ans = append(ans, x)
}
left = max(left, x)
}
return ans
}Complexity analysis
| 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 |
Frequently asked questions
Is Valid Elements in an Array easy or hard?
The problem is generally classified as Easy because the logic relies on basic array traversal and preprocessing. Once you recognize the prefix maximum and suffix minimum pattern, the implementation becomes straightforward with linear time complexity.
Valid Elements in an Array Python/Java solution
Implement the O(n) solution by first computing a suffix minimum array, then scanning from left to right while maintaining the maximum value so far. At each index, check whether the current element lies strictly between the prefix maximum and suffix minimum. The same logic works in Python, Java, and C++ with simple loops.
How to solve Valid Elements in an Array in O(n)?
Precompute a suffix minimum array where each position stores the smallest value to its right. Traverse the array from left to right while maintaining the maximum value seen so far. For each element, check if prefixMax < arr[i] < suffixMin[i+1]. This ensures the element satisfies both constraints in constant time per index.
What is the best approach for Valid Elements in an Array?
The most efficient approach uses prefix maximum and suffix minimum preprocessing. Compute the maximum value to the left of every index and the minimum value to the right. An element is valid if it is greater than the left maximum and smaller than the right minimum. This runs in O(n) time with O(n) extra space.
Is Valid Elements in an Array asked at Google/Amazon/Meta?
Problems involving prefix maximum and suffix minimum preprocessing appear frequently in interviews at large tech companies including Google and Amazon. The exact problem title may vary, but the pattern of validating elements based on left and right constraints is a common array interview concept.
What data structure is used in Valid Elements in an Array?
The problem mainly uses arrays for prefix and suffix preprocessing. A suffix minimum array stores the smallest value to the right of each index, while a running variable or prefix array tracks the maximum value seen on the left side.
What is the time complexity of Valid Elements in an Array?
The optimal solution runs in O(n) time because it processes the array in a few linear passes. One pass builds the suffix minimum array, another tracks prefix maximum values while checking validity. The brute force approach takes O(n^2) time due to repeated left and right scans.