Count Elements With Strictly Smaller and Greater Elements - Solution & Explanation
Problem Statement
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] <= 105
Approach Overview
Problem 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 1: Approach 1: Sorting Method
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.
Code
Python
JavaScript
Java
C#
C
Complexity
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.
Approach 2: Approach 2: Two-Pass Min/Max Analysis
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.
Code
Python
JavaScript
Java
C#
C
Complexity
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.
Approach 3: Find Minimum and Maximum Values
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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Count Elements With Strictly Smaller and Greater Elements | Leetcode 2148 | Weekly Contest 277|Java • Pepcoding • 3,717 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Elements With Strictly Smaller and Greater Elements easy or hard?
Count Elements With Strictly Smaller and Greater Elements Python/Java solution
How to solve Count Elements With Strictly Smaller and Greater Elements in O(n)?
Is Count Elements With Strictly Smaller and Greater Elements asked at Google/Amazon/Meta?
What is the best approach for Count Elements With Strictly Smaller and Greater Elements ?
What data structure is used in Count Elements With Strictly Smaller and Greater Elements ?
What is the time complexity of Count Elements With Strictly Smaller and Greater Elements ?
Ready to solve this problem?
Practice Count Elements With Strictly Smaller and Greater Elements with our built-in code editor and test cases.
Practice on FleetCode