3912. Valid Elements in an Array

EasyArray

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

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.

Explanation:

The problem asks you to scan through the array and pick out every element that "stands out" in at least one direction. Specifically, an element qualifies as valid in either of these two ways:

Greater than everything on its left: The element must be strictly larger than all elements that come before it. This effectively means the element is a new running maximum when reading the array from left to right.
Greater than everything on its right: The element must be strictly larger than all elements that come after it. This means the element is a running maximum when reading the array from right to left.

If an element meets either of these conditions, it is valid and should be included in the result.

A couple of important points to keep in mind:

The first element is always valid, because there are no elements to its left, so the condition "strictly greater than every element to its left" is trivially satisfied.
The last element is always valid, because there are no elements to its right, so the condition "strictly greater than every element to its right" is trivially satisfied.

You must return the valid elements in the same order they appear in the original array nums.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Prefix Sums?

This problem maps to Prefix Sums through a short path in the full flowchart.

Precomputing prefix max/min or sums answers queries at each position in constant time.

Open in Flowchart

Intuition

The key observation is that the two conditions for validity can each be checked using a "running maximum" idea.

For the first condition — "strictly greater than every element to its left" — instead of looking at every single element on the left for each position, we only need to know the maximum value seen so far on the left. If the current element beats that maximum, it automatically beats every element on the left. So we can keep a single variable, left, that tracks the largest value among all elements before the current one, and update it as we move forward.

For the second condition — "strictly greater than every element to its right" — we apply the same idea, but from the other direction. For each position, we want to know the maximum value among all elements to its right. Computing this on the fly while moving left to right is awkward, so we preprocess it: we build an array right, where right[i] stores the maximum value from index i to the end of the array. We fill this by scanning from right to left, since right[i] = max(right[i + 1], nums[i]).

Once we have the right array prepared, we make a single left-to-right pass over nums. At each element x at index i, we check whether it qualifies:

x > left — it is strictly greater than everything on its left.
i == n - 1 — it is the last element, which is always valid.
x > right[i + 1] — it is strictly greater than the maximum of everything on its right.

If any of these holds, we add x to the answer. After checking, we update left = max(left, x) so the running maximum stays correct for the next iteration.

This way, instead of repeatedly scanning left and right for each element (which would be slow), we reduce the work to a single preprocessing pass plus one main pass, making the whole process efficient.

Solution Approach

Solution 1: Preprocessing the Array

We can preprocess the array to compute the maximum value to the right of each element and store it in an array right.

First, let n be the length of nums. We create the array right of size n, initialized so that right[n - 1] = nums[n - 1] (the last element only has itself to its right). Then we scan from right to left, filling each position with the formula right[i] = max(right[i + 1], nums[i]). After this pass, right[i] holds the maximum value among nums[i], nums[i + 1], ..., nums[n - 1].

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. We start with left = 0 (note that this works under the assumption that array values allow this baseline; the first element is handled because its own condition or the running comparison covers it). For each element x at index i, if it satisfies any of the following conditions, we add it to the answer:

It is strictly greater than left (greater than everything on its left).
It is the last element of the array, i.e. i == n - 1 (always valid).
It is strictly greater than right[i + 1] (greater than everything on its right).

During the traversal, we continuously update the value of left with left = max(left, x), so it always reflects the largest element seen so far before the next index.

After the traversal, we return the answer array.

Data structures and patterns used:

Suffix maximum array (right): This is a classic preprocessing pattern where we precompute aggregate information (here, the maximum) over all suffixes, allowing each right-side check to be done in O(1) time.
Running maximum variable (left): Instead of storing a full prefix maximum array, we use a single variable since we only need the left maximum at the current position during a single forward pass.

Complexity analysis:

Time complexity: O(n), where n is the length of nums. We make one pass to build right and one pass to build the answer.
Space complexity: O(n) for the right array. The output array is not counted as extra space.

Example Walkthrough

Let's trace through the solution approach using a small example:

nums = [3, 1, 4, 2, 5]

Step 1: Build the suffix maximum array right

We have n = 5. We create right of size 5 and start from the rightmost element, filling it using right[i] = max(right[i + 1], nums[i]).

Index `i`	`nums[i]`	Computation	`right[i]`
4	5	`right[4] = nums[4]`	5
3	2	`max(right[4], 2) = max(5, 2)`	5
2	4	`max(right[3], 4) = max(5, 4)`	5
1	1	`max(right[2], 1) = max(5, 1)`	5
0	3	`max(right[1], 3) = max(5, 3)`	5

So after this pass:

right = [5, 5, 5, 5, 5]

Each right[i] now holds the maximum of nums[i..n-1].

Step 2: Traverse left to right, tracking left

We initialize left = 0 and check each element against the three conditions:

x > left (greater than everything on its left)
i == n - 1 (last element, always valid)
x > right[i + 1] (greater than everything on its right)

After each step we update left = max(left, x).

`i`	`x`	`x > left`?	last?	`x > right[i+1]`?	Valid?	New `left`
0	3	`3 > 0` �→ yes	no	`3 > right[1]=5` ✗	Yes	`max(0,3)=3`
1	1	`1 > 3` ✗	no	`1 > right[2]=5` ✗	No	`max(3,1)=3`
2	4	`4 > 3` ✗ wait `4>3`✓	no	`4 > right[3]=5` ✗	Yes	`max(3,4)=4`
3	2	`2 > 4` ✗	no	`2 > right[4]=5` ✗	No	`max(4,2)=4`
4	5	`5 > 4` ✓	yes	—	Yes	`max(4,5)=5`

Reading the results:

Index 0 (3): It's the first element, and as a new running maximum it's greater than everything on its left → valid.
Index 1 (1): Not greater than the left max (3), and not greater than the right max (5) → not valid.
Index 2 (4): It beats the current left max (3), so it's strictly greater than everything on its left → valid.
Index 3 (2): Smaller than both the left max (4) and right max (5) → not valid.
Index 4 (5): The last element, always valid; it's also greater than everything on its left → valid.

Final answer:

[3, 4, 5]

This matches our intuition: 3 and 4 stand out because they are new maxima from the left, while 5 is both the last element and the overall maximum, qualifying in both directions.

Solution Implementation

1class Solution:
2    def findValidElements(self, nums: list[int]) -> list[int]:
3        n = len(nums)
4
5        # suffix_max[i] holds the maximum value within nums[i:]
6        suffix_max = [nums[-1]] * n
7        for i in range(n - 2, -1, -1):
8            suffix_max[i] = max(suffix_max[i + 1], nums[i])
9
10        # prefix_max tracks the maximum value among elements seen before index i
11        prefix_max = 0
12        ans: list[int] = []
13
14        for i, x in enumerate(nums):
15            # An element is valid if it is strictly greater than everything
16            # to its left, or it is the last element, or it is strictly
17            # greater than everything to its right.
18            if x > prefix_max or i == n - 1 or x > suffix_max[i + 1]:
19                ans.append(x)
20            # Update the running prefix maximum after processing index i
21            prefix_max = max(prefix_max, x)
22
23        return ans
24```
25
26**A note on edge cases / alternative perspective:**
27
28The original code assumes `nums` is non-empty (the line `right = [nums[-1]] * n` would raise an `IndexError` on an empty list). If you want a robust version that handles the empty input gracefully, you could add a guard:
29
30```python3
31class Solution:
32    def findValidElements(self, nums: list[int]) -> list[int]:
33        n = len(nums)
34        if n == 0:
35            return []
36
37        # suffix_max[i] holds the maximum value within nums[i:]
38        suffix_max = [nums[-1]] * n
39        for i in range(n - 2, -1, -1):
40            suffix_max[i] = max(suffix_max[i + 1], nums[i])
41
42        prefix_max = 0          # max value among elements before index i
43        ans: list[int] = []
44
45        for i, x in enumerate(nums):
46            # Valid if greater than all on the left, last element,
47            # or greater than all on the right.
48            if x > prefix_max or i == n - 1 or x > suffix_max[i + 1]:
49                ans.append(x)
50            prefix_max = max(prefix_max, x)
51
52        return ans
53

1class Solution {
2    public List<Integer> findValidElements(int[] nums) {
3        int length = nums.length;
4
5        // maxFromRight[i] holds the maximum value among nums[i..length-1]
6        int[] maxFromRight = new int[length];
7        maxFromRight[length - 1] = nums[length - 1];
8        for (int i = length - 2; i >= 0; i--) {
9            maxFromRight[i] = Math.max(maxFromRight[i + 1], nums[i]);
10        }
11
12        // maxFromLeft tracks the maximum value among nums[0..i-1] as we iterate
13        int maxFromLeft = 0;
14        List<Integer> result = new ArrayList<>();
15
16        for (int i = 0; i < length; i++) {
17            int current = nums[i];
18
19            // An element is valid if it is greater than every element on its left,
20            // or it is the last element, or it is greater than the max on its right
21            if (current > maxFromLeft || i == length - 1 || current > maxFromRight[i + 1]) {
22                result.add(current);
23            }
24
25            // Update the running maximum from the left side
26            maxFromLeft = Math.max(maxFromLeft, current);
27        }
28
29        return result;
30    }
31}
32

1class Solution {
2public:
3    vector<int> findValidElements(vector<int>& nums) {
4        int n = nums.size();
5
6        // suffixMax[i] holds the maximum value among nums[i..n-1]
7        vector<int> suffixMax(n);
8        suffixMax[n - 1] = nums[n - 1];
9        for (int i = n - 2; i >= 0; i--) {
10            suffixMax[i] = max(suffixMax[i + 1], nums[i]);
11        }
12
13        // prefixMax tracks the maximum value among elements seen so far (strictly to the left)
14        int prefixMax = 0;
15        vector<int> result;
16
17        for (int i = 0; i < n; i++) {
18            int current = nums[i];
19
20            // An element is valid if it is strictly greater than everything to its left,
21            // or it is the last element, or it is strictly greater than everything to its right.
22            if (current > prefixMax || i == n - 1 || current > suffixMax[i + 1]) {
23                result.push_back(current);
24            }
25
26            // Update the running maximum of the elements to the left.
27            prefixMax = max(prefixMax, current);
28        }
29
30        return result;
31    }
32};
33

1/**
2 * Collects "valid" elements from the input array.
3 *
4 * An element nums[i] is considered valid when at least one of the
5 * following conditions holds:
6 *   1. It is strictly greater than every element to its left.
7 *   2. It is the last element of the array.
8 *   3. It is strictly greater than every element to its right.
9 *
10 * @param nums - The input array of numbers.
11 * @returns An array containing the valid elements in their original order.
12 */
13function findValidElements(nums: number[]): number[] {
14    const length: number = nums.length;
15
16    // rightMax[i] holds the maximum value within nums[i..length-1].
17    const rightMax: number[] = new Array<number>(length);
18    rightMax[length - 1] = nums[length - 1];
19    for (let i = length - 2; i >= 0; i--) {
20        rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
21    }
22
23    // leftMax tracks the maximum value seen so far to the left of i.
24    let leftMax = 0;
25    const result: number[] = [];
26
27    for (let i = 0; i < length; i++) {
28        const current: number = nums[i];
29
30        // Valid if it beats everything on the left, is the last element,
31        // or beats everything strictly on the right.
32        if (current > leftMax || i === length - 1 || current > rightMax[i + 1]) {
33            result.push(current);
34        }
35
36        // Update the running maximum for the elements to the left.
37        leftMax = Math.max(leftMax, current);
38    }
39
40    return result;
41}
42```
43
44**A note on a potential edge case:** the original code accesses `nums[n - 1]` and `right[n - 1]` without checking for an empty array. If `nums` could be empty, you'd want a guard clause at the top. Here's an alternative that handles that safely:
45
46```typescript
47function findValidElements(nums: number[]): number[] {
48    const length: number = nums.length;
49    if (length === 0) {
50        return [];
51    }
52
53    const rightMax: number[] = new Array<number>(length);
54    rightMax[length - 1] = nums[length - 1];
55    for (let i = length - 2; i >= 0; i--) {
56        rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
57    }
58
59    let leftMax = 0;
60    const result: number[] = [];
61
62    for (let i = 0; i < length; i++) {
63        const current: number = nums[i];
64        if (current > leftMax || i === length - 1 || current > rightMax[i + 1]) {
65            result.push(current);
66        }
67        leftMax = Math.max(leftMax, current);
68    }
69
70    return result;
71}
72

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array nums. The code performs two separate passes over the array: the first loop runs from n - 2 down to 0 to build the right array, taking O(n) time; the second loop iterates over all elements of nums once to construct the answer, also taking O(n) time. Since these loops are sequential rather than nested, the total time complexity is O(n) + O(n) = O(n).
Space Complexity: O(n), where n is the length of the array nums. The auxiliary right array stores one value for each element of nums, requiring O(n) extra space. The variable left uses only O(1) space, and the ans list is the output, which is typically not counted toward auxiliary space. Therefore, the dominant extra space usage is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Initializing `prefix_max = 0` breaks with negative numbers

The most subtle and dangerous bug in this solution is the baseline prefix_max = 0. The logic relies on the comparison x > prefix_max to detect whether x is a new running maximum from the left. By starting at 0, the code implicitly assumes that all values in nums are positive.

Consider the input nums = [-5, -3, -8]:

At i = 0, x = -5. The check x > prefix_max becomes -5 > 0, which is False. The first element relies on the i == n - 1 clause or the right-side check to be included — but here neither saves it, so -5 is incorrectly excluded even though the first element is always valid.

Solution: Initialize prefix_max to negative infinity, or special-case the first element explicitly.

class Solution:
    def findValidElements(self, nums: list[int]) -> list[int]:
        n = len(nums)
        if n == 0:
            return []

        suffix_max = [nums[-1]] * n
        for i in range(n - 2, -1, -1):
            suffix_max[i] = max(suffix_max[i + 1], nums[i])

        prefix_max = float('-inf')   # safe baseline for any integer values
        ans: list[int] = []

        for i, x in enumerate(nums):
            if x > prefix_max or i == n - 1 or x > suffix_max[i + 1]:
                ans.append(x)
            prefix_max = max(prefix_max, x)

        return ans

With this fix, at i = 0 the check -5 > -inf is True, so the first element is always correctly included.

Pitfall 2: Off-by-one error when accessing `suffix_max[i + 1]`

The right-side check is written as x > suffix_max[i + 1], not x > suffix_max[i]. This is intentional and critical:

suffix_max[i] includes nums[i] itself, so x > suffix_max[i] would always be False (an element can never be strictly greater than a maximum that includes itself).
We want to compare against everything strictly to the right, which is suffix_max[i + 1].

If you carelessly write suffix_max[i], the right-side condition silently never fires, and you'd only ever capture left-side running maxima.

Why the order of the or clauses matters: The i == n - 1 clause must come before x > suffix_max[i + 1] in the or chain. When i == n - 1, the index i + 1 is out of bounds. Python short-circuits the or, so once i == n - 1 evaluates to True, the out-of-bounds suffix_max[i + 1] is never evaluated. Reordering these clauses would trigger an IndexError on the last element.

# Correct — short-circuits before the out-of-bounds access
if x > prefix_max or i == n - 1 or x > suffix_max[i + 1]:

# WRONG — raises IndexError when i == n - 1
if x > prefix_max or x > suffix_max[i + 1] or i == n - 1:

Pitfall 3: Forgetting the empty-array guard

As noted, suffix_max = [nums[-1]] * n evaluates nums[-1] eagerly. On an empty list this raises IndexError before the loops even begin. Always guard with if n == 0: return [] if empty input is possible.

Pitfall 4: Misreading "strictly greater" as "greater than or equal"

The conditions require strictly greater (>), not >=. Using >= would wrongly accept duplicates of the current maximum. For example, in nums = [3, 3], the second 3 is not strictly greater than the 3 on its left, so it qualifies only via the last-element rule — not via the left-side check. Using >= for prefix_max would incorrectly classify why elements are valid and could break related variants of the problem.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers