Count Elements With Strictly Smaller and Greater Elements Solution
Count Elements With Strictly Smaller and Greater Elements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Count Elements With Strictly Smaller and Greater Elements is an easy coding problem on arrays, sorting and counting, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Counting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return how many elements of nums have both a strictly smaller element and a strictly greater element somewhere in nums.
Each position counts on its own, so equal values are counted once per occurrence.
Example 1
Input: nums = [5,-3,8,5,-3]
Output: 2
Explanation: Both 5s have -3 below and 8 above; -3 has nothing smaller and 8 nothing larger.
Example 2
Input: nums = [4,4,4]
Output: 0
Example 3
Input: nums = [-100000,0,100000]
Output: 1
Constraints
1 <= nums.length <= 100-10^5 <= nums[i] <= 10^5
Hints for Count Elements With Strictly Smaller and Greater Elements
Hint 1
An element has something strictly smaller unless it is the minimum.
Hint 2
Likewise it has something strictly larger unless it is the maximum.
Hint 3
Find the minimum and maximum, then count the elements equal to neither.
How to solve Count Elements With Strictly Smaller and Greater Elements
An element qualifies exactly when it is neither the minimum nor the maximum of the array.
Approach
- Compute
lo = min(nums)andhi = max(nums). - Count the elements
xwithlo < x < hi.
Why it works
If x > lo, the minimum itself is a strictly smaller element; if x == lo, nothing is smaller. The same argument with the maximum handles 'strictly greater'. So x qualifies if and only if lo < x < hi; when all elements are equal, lo == hi and the count is 0.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Every copy of the minimum and of the maximum is excluded, not just one.
- With only one or two distinct values the answer is 0 — the test
lo < x < hihandles that without a special case. - Values can be negative; do not start the running maximum at 0.
Reference solution
Python
from typing import List
def countElements(nums: List[int]) -> int:
lo, hi = min(nums), max(nums)
return sum(1 for x in nums if lo < x < hi)Java
public static int countElements(int[] nums) {
int lo = nums[0], hi = nums[0];
for (int v : nums) {
lo = Math.min(lo, v);
hi = Math.max(hi, v);
}
int count = 0;
for (int v : nums) {
if (v > lo && v < hi) count++;
}
return count;
}C++
int countElements(vector<int>& nums) {
int lo = *min_element(nums.begin(), nums.end());
int hi = *max_element(nums.begin(), nums.end());
int count = 0;
for (int v : nums) {
if (v > lo && v < hi) count++;
}
return count;
}JavaScript
var countElements = function(nums) {
var lo = nums[0], hi = nums[0];
for (var i = 1; i < nums.length; i++) {
if (nums[i] < lo) lo = nums[i];
if (nums[i] > hi) hi = nums[i];
}
var count = 0;
for (var j = 0; j < nums.length; j++) {
if (nums[j] > lo && nums[j] < hi) count++;
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms