Given an integer array nums, return the number of elements that have both a strictly smaller and a strictly greater element appear in nums.
Example 1:
Input: nums = [11,7,2,15]
Output: 2
Explanation: The element 7 has the element 2 strictly smaller than it and the element 11 strictly greater than it.
Element 11 has element 7 strictly smaller than it and element 15 strictly greater than it.
In total there are 2 elements having both a strictly smaller and a strictly greater element appear in nums.
Example 2:
Input: nums = [-3,3,3,90]
Output: 2
Explanation: The element 3 has the element -3 strictly smaller than it and the element 90 strictly greater than it.
Since there are two elements with the value 3, in total there are 2 elements having both a strictly smaller and a strictly greater element appear in nums.
Constraints:
1 <= nums.length <= 100-105 <= nums[i] <= 105Problem Overview: You are given an integer array. Count how many elements have at least one strictly smaller value and at least one strictly greater value somewhere else in the array. Elements equal to the global minimum or maximum cannot satisfy this condition.
Approach 1: Sorting Method (O(n log n) time, O(1) extra space)
Sort the array first using a standard sorting algorithm. After sorting, the smallest values appear at the beginning and the largest values at the end. Any element strictly between these extremes automatically has both a smaller and a greater value in the array.
Iterate from index 1 to n-2. For each value, check if it is different from the first element (global minimum) and different from the last element (global maximum). If both conditions hold, increment the count. Sorting simplifies the comparison logic because the boundaries of the array represent the global extremes.
This approach is easy to reason about and useful when the array may already be sorted or when sorting is needed for additional operations. The tradeoff is the O(n log n) sorting cost.
Approach 2: Two-Pass Min/Max Analysis (O(n) time, O(1) space)
The optimal solution avoids sorting entirely. First scan the array once to compute the global minimum and maximum values. These represent the only values that cannot satisfy the requirement because they lack either a smaller or greater counterpart.
In the second pass, iterate through the array and count elements whose value is strictly greater than min and strictly less than max. Every such element automatically has at least one smaller element (the minimum) and one greater element (the maximum). This turns the problem into a simple filtering step over the array.
The algorithm relies only on basic array traversal and constant tracking variables, making it both cache‑friendly and simple to implement. No additional data structures are required beyond a few variables used for counting and comparisons.
Recommended for interviews: The two-pass min/max scan is the expected answer. It demonstrates awareness that only the global extremes matter, reducing the problem to two linear scans with O(n) time and O(1) space. Mentioning the sorting approach first shows you considered a straightforward strategy, while the min/max analysis demonstrates optimization skills commonly tested in counting and array problems.
This approach involves sorting the given array to easily identify the smallest and largest elements. After sorting, all elements except the first one (smallest) and the last one (largest) can be considered for counting. This method is straightforward because sorting gives a clear view of how elements compare to each other.
This Python solution first sorts the array, and then identifies the smallest and largest elements as the first and last elements of the sorted array, respectively. It then counts how many elements lie strictly between these two values.
Python
JavaScript
Java
C#
C
Time Complexity: O(n log n) due to the sorting step.
Space Complexity: O(1) because the space used doesn't depend on input size apart from the input array.
In this approach, we do not sort the array. Instead, the algorithm involves two separate passes through the array. In the first pass, it finds the minimum and maximum values. In the second pass, it counts elements that are strictly greater than the minimum and strictly less than the maximum. This approach avoids the sorting step, potentially improving performance for larger datasets.
This Python implementation finds the minimum and maximum values of the array in the first pass. In the second pass, it counts the elements that lie strictly between the found minimum and maximum values.
Python
JavaScript
Java
C#
C
Time Complexity: O(n) because it iterates over the list twice but still effectively linear.
Space Complexity: O(1) because no extra space is used apart from variables for min and max.
According to the problem description, we can first find the minimum value mi and the maximum value mx of the array nums. Then, traverse the array nums and count the number of elements that satisfy mi < x < mx.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Sorting Method | Time Complexity: O(n log n) due to the sorting step. |
| Approach 2: Two-Pass Min/Max Analysis | Time Complexity: O(n) because it iterates over the list twice but still effectively linear. |
| Find Minimum and Maximum Values | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting Method | O(n log n) | O(1) | When sorting is acceptable or the array is already sorted |
| Two-Pass Min/Max Analysis | O(n) | O(1) | Best general solution; optimal linear scan without sorting |
Count Elements With Strictly Smaller and Greater Elements | Leetcode 2148 | Weekly Contest 277|Java • Pepcoding • 3,667 views views
Watch 9 more video solutions →Practice Count Elements With Strictly Smaller and Greater Elements with our built-in code editor and test cases.
Practice on FleetCode