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.

Walkthrough

Brute force

Ok, so when I see this the first thing I'm thinking is that we've got a left and a right element going on. We could look to try to solve these sub problems straight away But let's start completely from the beginning with the brute force approach. Doing this we demonstrate that the understand the problem and how we work to optimise it. To do this we can simply iterate over the list checking if it's greater than the max of the left and right elements.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
  def findValidElements(self, nums: list[int]) -> list[int]:
    valid_values = []

    # Edge case: empty list
    if nums == []:
      return valid_values

    for idx, value in enumerate(nums):
      # Leftmost and rightmost elements are valid by definition
      if idx == 0 or idx == len(nums) - 1:
        valid_values.append(value)
        continue

      # Check if it's left-valid OR right-valid
      if value > max(nums[:idx]) or value > max(nums[idx+1:]):
        valid_values.append(value)

    return valid_values

Submission result

Now for each element we're testing we have to scan the whole list to the left and right. So that's n-1 values we have to process, and we have n-2 values to test - we don't need to include the edge ones. That means this is firmly O(n^2). It'll work but clearly there's a lot of wasted work here.

Partial optimisation

Let's think about what that wasted work actually is. Each time we move along we're completely recalculating the max of the leftmost elements. But we knew what it was last iteration, and we know what the new element that's just gone in so we don't need to look at the whole list again. To know what the max value is. So, it would be natural now to think: I can just track the leftmost max by updating the max to be max(last_max, new_value). And you'd be right - but this is one of those times where you need to take a step back and remember what the problem is. A value is valid if it's greater than all things to its left. That means the last valid value must be strictly the maximum of the values in the left. So we can just track this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
  def findValidElements(self, nums: list[int]) -> list[int]:
    valid_values = []

    # Edge case: empty list
    if nums == []:
      return valid_values

    max_left = nums[0]
    for idx, value in enumerate(nums):
      # Leftmost and rightmost elements are valid by definition
      if idx == 0 or idx == len(nums) - 1:
        valid_values.append(value)
        continue

      if value > max_left:
        valid_values.append(value)
        max_left = value
      elif value > max(nums[idx+1:]):
        valid_values.append(value)

    return valid_values

Submission result

That's removed half of our computation, which means we're now on average checking half as many elements: n/2. We're now at (n / 2) * (n - 2) which is still O(n^2) but we can see if we can eliminate the right half then we'll be down at O(n).

Final solution

The issue we have here is that we're trying to do left-valid and right-valid at the same time. We can optimise the right-valid check by mirroring what we did for left-valid but starting at the last element and working backwards. In that case we'll always know the max on the right hand side was the last right-valid element. But we have the same problem if we focus on right-valid we have to do the max calculation for left-valid.

The next step would be to ask the question can we do them separately. One O(n) pass for left-valid then one O(n) pass for right-valid.

It's at this point that people often get themselves in a twist thinking they can't do this because we have to have the valid values in order, and what if there's a right-valid value in the middle of the left-valid items. Then you may start thinking about storing the index and the value, then sorting them together. Sorting is O(n log n), so better than O(n^2) but it feels like there should be an O(n) solution here.

The key observation is to go back and think about the question. If you were to try a few examples what does the output look like. If you print them out then what we have is an ascending list of values (left-valid) Then a descending list of values (right-valid). It is impossible to have a right-valid entry within a section of left-valid. If that would happen then the value must be bigger, in which case it's left-valid!

The only exception is the inflection point. Consider the sequence: 1,2,3,2,1 1,2,3 are all left-valid and 3,2,1 are right-valid. So the 3 is both left- and right-valid. Here we just need to make sure we don't include 3 in the list twice.

Consider the sequence: 1,2,3,3,2,1 Here the 1,2,3 are all left-valid, and 3,2,1 are all right-valid. There is no overlap, and we can have a repeated number.

Knowing this we could work from each side towards the centre. However, you end up with a lot of bookkeeping in the code doing that. Instead we can do it in two passes. First we do the left-valid items, then we do the right-valid items on the subset of the items starting after the last left-valid item.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
  def findValidElements(self, nums: list[int]) -> list[int]:
    valid_values = []

    # Edge case: empty list
    if nums == []:
      return valid_values

    # Do the left-pass.
    max_idx = 0
    for idx, value in enumerate(nums):
      # Leftmost element is valid by definition
      if idx == 0:
        valid_values.append(value)
        continue

      if value > valid_values[-1]:
        valid_values.append(value)
        max_idx = idx

    # Right pass over remaining elements.
    right_valids = []
    for value in nums[:max_idx:-1]:
      if not right_valids or value > right_valids[-1]:
        right_valids.append(value)

    return valid_values + right_valids[::-1]

Submission result

This will take about 2*n in the worst case, where the first and last values are the only valid ones. Starting at the last left-valid saves us max_idx comparisons, which can be anywhere from 0 to n-1. It is still O(n) in total.