LeetCode 2148 - Count Elements With Strictly Smaller and Greater Elements

The problem gives us an integer array nums and asks us to count how many elements satisfy a very specific condition.

leetcodeeasyarraysortingcounting

LeetCode Problem 2148

Difficulty: 🟢 Easy
Topics: Array, Sorting, Counting

Solution

Problem Understanding

The problem gives us an integer array nums and asks us to count how many elements satisfy a very specific condition.

For an element nums[i] to be counted, there must exist:

  • at least one element in the array that is strictly smaller than nums[i]
  • at least one element in the array that is strictly greater than nums[i]

In other words, the element cannot be the minimum value in the array, and it also cannot be the maximum value in the array.

The input is a list of integers, and the output is a single integer representing how many elements meet this requirement.

For example, in the array [11,7,2,15]:

  • 2 is the smallest value, so it does not have a strictly smaller element
  • 15 is the largest value, so it does not have a strictly greater element
  • 7 and 11 both have smaller and greater values somewhere in the array

Therefore, the answer is 2.

The constraints are small:

  • 1 <= nums.length <= 100
  • -10^5 <= nums[i] <= 10^5

Since the array size is at most 100, even an O(n^2) solution would be fast enough. However, the problem has a much simpler and more efficient observation that leads to a linear-time solution.

Some important edge cases are worth identifying early:

  • Arrays with only one element cannot contain any valid elements.
  • Arrays where all values are equal also produce 0.
  • Duplicate minimum or duplicate maximum values should not be counted.
  • Duplicate middle values should all be counted if they have both smaller and greater values present.

For example:

  • [1] returns 0
  • [5,5,5] returns 0
  • [1,2,2,3] returns 2, because both 2s qualify

Approaches

Brute Force Approach

The most direct solution is to examine every element individually and check whether there exists:

  • another element smaller than it
  • another element greater than it

For each element nums[i], we scan the entire array again and track whether we have found both conditions. If both are satisfied, we increment the answer.

This approach is correct because it explicitly verifies the problem definition for every element. However, it performs nested iteration over the array.

Since there are n elements, and each element may scan all n elements again, the total complexity becomes O(n^2).

Although this is acceptable for n <= 100, it is not the cleanest or most optimal solution.

Optimal Approach

The key observation is that an element is valid if and only if it is neither:

  • the minimum value in the array
  • nor the maximum value in the array

Why is this true?

  • If an element equals the minimum value, there cannot be a strictly smaller element.
  • If an element equals the maximum value, there cannot be a strictly greater element.
  • Every value strictly between the minimum and maximum automatically satisfies both conditions.

So the problem reduces to:

  1. Find the minimum value.
  2. Find the maximum value.
  3. Count how many elements are strictly between them.

This gives a simple linear-time solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Check every element against all others
Optimal O(n) O(1) Count elements strictly between min and max

Algorithm Walkthrough

Optimal Algorithm

  1. Initialize two variables, minimum_value and maximum_value, using the smallest and largest values in the array.

We can compute these efficiently using built-in operations like min(nums) and max(nums). 2. Initialize a counter variable count to 0.

This variable will store how many valid elements we find. 3. Iterate through every element in nums.

For each number:

  • check whether it is strictly greater than minimum_value
  • check whether it is strictly less than maximum_value
  1. If both conditions are true, increment count.

This means the current element has at least one smaller element and at least one greater element somewhere in the array. 5. After processing all elements, return count.

Why it works

The algorithm relies on a simple invariant:

  • Every element equal to the global minimum lacks a strictly smaller value.
  • Every element equal to the global maximum lacks a strictly greater value.
  • Every element strictly between them automatically has both.

Because the algorithm counts exactly the elements strictly between the minimum and maximum values, it counts precisely the valid elements required by the problem.

Python Solution

from typing import List

class Solution:
    def countElements(self, nums: List[int]) -> int:
        minimum_value = min(nums)
        maximum_value = max(nums)

        count = 0

        for number in nums:
            if minimum_value < number < maximum_value:
                count += 1

        return count

The implementation starts by computing the minimum and maximum values in the array. These two values define the boundary of valid elements.

Next, the code iterates through every number in the array. For each value, it checks whether the number lies strictly between the minimum and maximum values.

If it does, the counter is incremented.

Finally, the function returns the total count.

The implementation uses constant extra space and performs only a single traversal after computing the minimum and maximum values.

Go Solution

func countElements(nums []int) int {
    minimumValue := nums[0]
    maximumValue := nums[0]

    for _, number := range nums {
        if number < minimumValue {
            minimumValue = number
        }

        if number > maximumValue {
            maximumValue = number
        }
    }

    count := 0

    for _, number := range nums {
        if number > minimumValue && number < maximumValue {
            count++
        }
    }

    return count
}

The Go implementation follows the same logic as the Python solution.

Since Go does not provide built-in min() and max() functions for slices, we manually compute the minimum and maximum values using a loop.

The constraints are small enough that integer overflow is not a concern. The function also safely handles arrays of length 1, because the initial minimum and maximum values are both assigned from nums[0].

Worked Examples

Example 1

Input:

nums = [11,7,2,15]

First, compute:

Variable Value
minimum_value 2
maximum_value 15

Now iterate through the array.

Current Number Between 2 and 15? Count
11 Yes 1
7 Yes 2
2 No, equal to minimum 2
15 No, equal to maximum 2

Final answer:

2

Example 2

Input:

nums = [-3,3,3,90]

First, compute:

Variable Value
minimum_value -3
maximum_value 90

Now iterate through the array.

Current Number Between -3 and 90? Count
-3 No, equal to minimum 0
3 Yes 1
3 Yes 2
90 No, equal to maximum 2

Final answer:

2

Complexity Analysis

Measure Complexity Explanation
Time O(n) We scan the array a constant number of times
Space O(1) Only a few extra variables are used

The algorithm performs one pass to determine the minimum and maximum values and another pass to count valid elements. Since each pass is linear, the total time complexity remains O(n).

The space complexity is constant because the algorithm only stores a few integer variables regardless of input size.

Test Cases

from typing import List

class Solution:
    def countElements(self, nums: List[int]) -> int:
        minimum_value = min(nums)
        maximum_value = max(nums)

        count = 0

        for number in nums:
            if minimum_value < number < maximum_value:
                count += 1

        return count

solution = Solution()

assert solution.countElements([11, 7, 2, 15]) == 2  # Provided example
assert solution.countElements([-3, 3, 3, 90]) == 2  # Duplicate middle values
assert solution.countElements([1]) == 0  # Single element
assert solution.countElements([5, 5, 5]) == 0  # All equal
assert solution.countElements([1, 2, 3]) == 1  # Only middle element counts
assert solution.countElements([1, 1, 2, 2, 3, 3]) == 2  # Duplicate min/max
assert solution.countElements([-10, 0, 10]) == 1  # Negative and positive values
assert solution.countElements([2, 2, 2, 3]) == 0  # No strictly smaller for 2
assert solution.countElements([1, 2, 2, 2, 3]) == 3  # Multiple valid duplicates
assert solution.countElements([100000, -100000, 0]) == 1  # Constraint extremes
Test Why
[11,7,2,15] Validates the first provided example
[-3,3,3,90] Verifies duplicate middle values
[1] Tests minimum array size
[5,5,5] Tests all identical values
[1,2,3] Tests a simple increasing array
[1,1,2,2,3,3] Ensures duplicate min/max values are excluded
[-10,0,10] Verifies handling of negative numbers
[2,2,2,3] Tests absence of strictly smaller elements
[1,2,2,2,3] Confirms all valid duplicates are counted
[100000,-100000,0] Tests constraint boundary values

Edge Cases

Array with only one element

An array like [7] cannot contain any valid elements because there is no other value in the array at all.

A naive implementation might accidentally count the single element if it does not properly enforce both conditions. The current implementation handles this correctly because the minimum and maximum values are both 7, so no number satisfies:

minimum_value < number < maximum_value

All elements are equal

Consider [4,4,4,4].

Every element is simultaneously the minimum and maximum value. Since the problem requires strictly smaller and strictly greater elements, none of these values qualify.

The implementation correctly returns 0 because no element is strictly between the minimum and maximum values.

Duplicate minimum or maximum values

Consider [1,1,2,3,3].

The duplicate 1s should not be counted because there is no strictly smaller value than 1. Similarly, the duplicate 3s should not be counted because there is no strictly greater value than 3.

A buggy implementation might incorrectly count duplicates if it only checks for existence of different indices rather than strictly different values.

The current solution avoids this issue entirely by comparing directly against the global minimum and maximum values.