Skip to main content
Talentd

Valid Elements in an Array - Solution & Explanation

EasyArray8 min read
Practice this problem

Problem Statement

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] 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.
  • 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 <= 100
  • 1 <= 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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Left and Right ChecksO(n^2)O(1)Small arrays or quick prototype to validate logic
Prefix Max and Suffix Min ArraysO(n)O(n)General case and most common interview solution
Running Prefix Max + Suffix MinO(n)O(n)Cleaner implementation with fewer stored arrays

Video Solution

Valid Elements in an Array | LeetCode 3912 | Weekly Contest 499 | Java Code | Developer Coder • Developer Coder • 359 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice Valid Elements in an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays