Watch 10 video solutions for Count Elements With Strictly Smaller and Greater Elements , a easy level problem involving Array, Sorting, Counting. This walkthrough by Pepcoding has 3,667 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |