Problem Description

You are given an integer array nums. Your task is to count how many elements in the array have both a strictly smaller element AND a strictly greater element that also appear somewhere in the array.

In other words, for an element to be counted:

• There must be at least one element in nums that is strictly less than it
• There must be at least one element in nums that is strictly greater than it

The solution works by finding the minimum value mi and maximum value mx in the array. Then it counts all elements x where mi < x < mx. This works because:

• Any element equal to the minimum value cannot have a smaller element in the array
• Any element equal to the maximum value cannot have a greater element in the array
• All elements strictly between the minimum and maximum will have both smaller and greater elements present

For example, if nums = [3, 1, 5, 1, 3]:

• Minimum is 1, maximum is 5
• Elements strictly between 1 and 5 are: two occurrences of 3
• So the answer is 2

Intuition

The key insight is recognizing that we don't need to check every element against every other element to find which ones have both smaller and greater values.

Think about the extreme elements in the array - the minimum and maximum values. The minimum value can never have an element smaller than it (by definition), so it can never be counted. Similarly, the maximum value can never have an element greater than it, so it also can never be counted.

Now consider any element that's not at these extremes - any element strictly between the minimum and maximum. Such an element is guaranteed to have:

• At least one smaller element (the minimum value itself)
• At least one greater element (the maximum value itself)

This means we can simplify our problem dramatically. Instead of checking each element to see if it has both smaller and greater elements in the array, we just need to:

1. Find the minimum value mi and maximum value mx
2. Count all elements where mi < x < mx

This transforms what could be an O(n²) problem (checking each element against all others) into an O(n) problem (one pass to find min/max, one pass to count valid elements).

The elegance of this approach lies in recognizing that the existence of smaller and greater elements is determined entirely by an element's relationship to the array's extremes.

Learn more about Sorting patterns.

Solution Approach

The implementation follows a straightforward two-step process:

Step 1: Find the minimum and maximum values

We use Python's built-in min() and max() functions to find the smallest and largest elements in the array:

mi, mx = min(nums), max(nums)

This requires one pass through the array for each function, giving us O(n) time complexity for this step.

Step 2: Count elements strictly between min and max

We use a generator expression with the sum() function to count how many elements satisfy the condition mi < x < mx:

return sum(mi < x < mx for x in nums)

This works because:

• The expression mi < x < mx evaluates to True (which equals 1) when x is strictly between the minimum and maximum
• It evaluates to False (which equals 0) otherwise
• sum() adds up all these 1s and 0s, effectively counting the True cases

The generator expression iterates through each element in nums exactly once, checking if it falls strictly between mi and mx. This is another O(n) operation.

Time Complexity: O(n) where n is the length of the array - we traverse the array three times (once for min, once for max, once for counting)

Space Complexity: O(1) - we only use two variables (mi and mx) regardless of input size

The beauty of this solution is its simplicity - by identifying that only elements strictly between the minimum and maximum can satisfy the condition, we avoid nested loops and achieve optimal linear time complexity.

Example Walkthrough

Let's walk through the solution with nums = [11, 7, 2, 15, 7]:

Step 1: Find the minimum and maximum values

• Scan through the array: [11, 7, 2, 15, 7]
• Minimum value mi = 2
• Maximum value mx = 15

Step 2: Count elements strictly between min and max

• Check each element to see if 2 < x < 15:
  • x = 11: Is 2 < 11 < 15? Yes ✓ (count = 1)
  • x = 7: Is 2 < 7 < 15? Yes ✓ (count = 2)
  • x = 2: Is 2 < 2 < 15? No ✗ (2 is not strictly greater than 2)
  • x = 15: Is 2 < 15 < 15? No ✗ (15 is not strictly less than 15)
  • x = 7: Is 2 < 7 < 15? Yes ✓ (count = 3)

Result: 3 elements satisfy the condition

Let's verify our answer makes sense:

• The element 11 has smaller elements (7, 2) and a greater element (15) ✓
• The first 7 has a smaller element (2) and greater elements (11, 15) ✓
• The element 2 (minimum) has no smaller elements ✗
• The element 15 (maximum) has no greater elements ✗
• The second 7 has a smaller element (2) and greater elements (11, 15) ✓

The count of 3 matches our expectation - only the elements strictly between the minimum and maximum have both smaller and greater elements in the array.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• Finding the minimum value using min(nums) requires traversing all n elements once: O(n)
• Finding the maximum value using max(nums) requires traversing all n elements once: O(n)
• The generator expression sum(mi < x < mx for x in nums) iterates through all n elements once to count elements strictly between the minimum and maximum: O(n)
• Total: O(n) + O(n) + O(n) = O(3n) = O(n)

The space complexity is O(1). This is because:

• The variables mi and mx store single integer values, using constant space
• The generator expression in sum() doesn't create an intermediate list but evaluates elements one by one
• No additional data structures are created that scale with the input size
• Only a constant amount of extra space is used regardless of the input size

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

Common Pitfalls

1. Handling Arrays with All Same Elements

A common oversight is not considering what happens when all elements in the array are identical. In this case, min_value == max_value, and no element can satisfy min_value < num < max_value.

Example:

nums = [5, 5, 5, 5]
# min_value = 5, max_value = 5
# No element can be strictly between 5 and 5
# Expected output: 0

Solution: The current implementation handles this correctly since the condition min_value < num < max_value will never be true when min equals max. No special handling needed, but it's important to test this edge case.

2. Confusion Between "Different Elements" vs "Different Values"

Developers might misinterpret the problem as requiring different element positions rather than different values. The problem asks if there exists at least one smaller and one greater value in the array, not necessarily at different indices.

Example:

nums = [1, 2, 2, 3]
# Both 2s should be counted since 1 < 2 < 3
# Correct output: 2 (both occurrences of 2)
# Wrong interpretation might count only 1

Solution: The implementation correctly counts all occurrences of values between min and max, not unique values.

3. Attempting to Optimize with Early Termination

Some might try to "optimize" by stopping early if they find min == max:

# Incorrect "optimization"
def countElements(self, nums: List[int]) -> int:
    if len(nums) <= 2:  # Wrong assumption!
        return 0
    min_value = min(nums)
    max_value = max(nums)
    if min_value == max_value:  # Unnecessary check
        return 0
    return sum(min_value < num < max_value for num in nums)

Problem: The length check is incorrect - an array like [1, 2, 3] has length 3 and should return 1, not 0.

Solution: Stick with the simple implementation. The overhead of additional checks often isn't worth the complexity, and the condition naturally handles edge cases.

4. Using Set for "Optimization" Without Considering Duplicates

Converting to a set might seem like an optimization but loses count information:

# Incorrect approach
def countElements(self, nums: List[int]) -> int:
    unique_nums = set(nums)  # Loses duplicate counts!
    min_value = min(unique_nums)
    max_value = max(unique_nums)
    return sum(min_value < num < max_value for num in unique_nums)

Example where this fails:

nums = [1, 2, 2, 2, 3]
# Correct answer: 3 (three 2s)
# Wrong answer with set: 1 (only one 2 in the set)

Solution: Work with the original array to preserve duplicate counts, as the original implementation does.