Skip to content

3912. Valid Elements in an Array

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.

Β 

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

Solutions

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 \(\textit{right}\).

Then, we traverse the array from left to right, using a variable \(\textit{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 \(\textit{left}\).
  • It is the last element of the array.
  • It is strictly greater than \(\textit{right}[i + 1]\).

During the traversal, we continuously update the value of \(\textit{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 \(\textit{nums}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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 ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class 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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
}

Comments