Count Elements With Strictly Smaller and Greater Elements
EasyPrompt
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:
numsExample 2:
nums
Constraints:
1 <= nums.length <= 100-105 <= nums[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through each element of the array. For each element, it performs another full scan of the array to determine if there exists at least one strictly smaller element and at least one strictly greater element.
Algorithm
- Initialize a counter
countto zero. - Loop through the array with an outer loop, picking one element
currentElementat a time. - For each
currentElement, use an inner loop to iterate through the entire array again. - Inside the inner loop, maintain two boolean flags:
foundSmallerandfoundGreater, both initiallyfalse. - Compare
currentElementwith every other elementotherElementin the array. - If
otherElement < currentElement, setfoundSmallertotrue. - If
otherElement > currentElement, setfoundGreatertotrue. - If after the inner loop completes, both
foundSmallerandfoundGreateraretrue, it meanscurrentElementsatisfies the condition. Increment thecount. - After the outer loop finishes,
countwill hold the total number of such elements.
Walkthrough
We can solve this problem by checking the condition for each element one by one. For every element nums[i] in the array, we iterate through the entire array again to check for two things: if there's any element nums[j] that is strictly smaller than nums[i], and if there's any element nums[k] that is strictly greater than nums[i]. We use two boolean flags, hasSmaller and hasGreater, to keep track of these conditions. If, after checking all other elements, both flags are true, we increment our result counter. We repeat this process for every element in the input array.
class Solution { public int countElements(int[] nums) { int count = 0; for (int i = 0; i < nums.length; i++) { boolean hasSmaller = false; boolean hasGreater = false; for (int j = 0; j < nums.length; j++) { if (nums[j] < nums[i]) { hasSmaller = true; } if (nums[j] > nums[i]) { hasGreater = true; } } if (hasSmaller && hasGreater) { count++; } } return count; }}Complexity
Time
O(n^2), where n is the number of elements in `nums`. For each of the n elements, we iterate through the entire array again, leading to n*n operations.
Space
O(1), as we only use a few extra variables for counting and flags, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space.
Cons
Highly inefficient for large inputs due to the quadratic time complexity.
Performs many redundant comparisons.
A more efficient approach is to first sort the array. Once sorted, an element has a strictly smaller and a strictly greater element if and only if it is not the minimum or maximum value in the array. This is because the smallest element in the sorted array will be a candidate for the 'strictly smaller' element, and the largest for the 'strictly greater' one.
Algorithm
- Sort the input array
numsin non-decreasing order. - If the array has fewer than 3 elements, it's impossible to satisfy the condition, so return 0.
- Identify the minimum value (
minVal = nums[0]) and the maximum value (maxVal = nums[n-1]). - Initialize a counter
countto zero. - Iterate through the sorted array. For each element
num, check if it is strictly greater thanminValand strictly less thanmaxVal. - If
num > minValandnum < maxVal, increment thecount. - Return the final
count.
Walkthrough
The core idea is that after sorting, the minimum element will be at the beginning of the array (nums[0]) and the maximum element will be at the end (nums[n-1]). Any element x that satisfies the condition min(nums) < x < max(nums) will have a strictly smaller element (the array's minimum) and a strictly greater element (the array's maximum). So, we first sort the array. Then, we find the minimum and maximum values. Finally, we iterate through the array and count how many elements fall strictly between these two values.
import java.util.Arrays; class Solution { public int countElements(int[] nums) { if (nums.length < 3) { return 0; } Arrays.sort(nums); int minVal = nums[0]; int maxVal = nums[nums.length - 1]; int count = 0; // We can skip the first and last elements as they can't be between min and max. for (int i = 1; i < nums.length - 1; i++) { if (nums[i] > minVal && nums[i] < maxVal) { count++; } } return count; }}Complexity
Time
O(n log n), which is dominated by the sorting step. The subsequent scan of the array takes O(n) time.
Space
O(log n) to O(n), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitives has an average space complexity of O(log n) for the recursion stack.
Trade-offs
Pros
Significantly faster than the brute-force approach for larger arrays.
The logic after sorting is very straightforward.
Cons
The sorting step can be overkill, as a linear time solution exists.
It might modify the input array, which could be undesirable in some contexts. A copy would use O(n) space.
The most efficient approach involves realizing that we only need to count the elements that are not the minimum and not the maximum value in the array. This can be achieved in linear time by first finding the minimum and maximum elements and then counting the numbers that fall between them.
Algorithm
- Find the minimum element
minValand maximum elementmaxValinnumsby iterating through the array once. - Initialize
count = 0. - Iterate through
numsa second time. - For each element
num, ifnum > minValandnum < maxVal, incrementcount. - Return
count.
Walkthrough
An element x has a strictly smaller and a strictly greater element if and only if x is not the global minimum and not the global maximum of the array. If x is not the minimum, then the global minimum is strictly smaller than x. If x is not the maximum, then the global maximum is strictly greater than x. This simplifies the problem to: 1. Find the minimum and maximum values in the array. 2. Count how many elements are strictly between this minimum and maximum. This can be implemented in two passes over the array.
class Solution { public int countElements(int[] nums) { if (nums.length < 3) { return 0; } int minVal = Integer.MAX_VALUE; int maxVal = Integer.MIN_VALUE; // First pass: find min and max for (int num : nums) { minVal = Math.min(minVal, num); maxVal = Math.max(maxVal, num); } // If all elements are the same, no element can satisfy the condition if (minVal == maxVal) { return 0; } int count = 0; // Second pass: count elements between min and max for (int num : nums) { if (num > minVal && num < maxVal) { count++; } } return count; }}Complexity
Time
O(n). We perform two passes over the array, each taking O(n) time. Thus, the total time complexity is O(n) + O(n) = O(n).
Space
O(1). We only use a few variables to store the min, max, and count, regardless of the input size.
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal space complexity of O(1).
Does not require modifying the input array.
Cons
Requires two passes over the data, though this is a minor drawback given the overall linear time complexity.
Solutions
Solution
class Solution {public int countElements(int[] nums) { int mi = 1000000, mx = -1000000; for (int num : nums) { mi = Math.min(mi, num); mx = Math.max(mx, num); } int ans = 0; for (int num : nums) { if (mi < num && num < mx) { ++ans; } } return ans; }}class Solution {public: int countElements(vector<int> &nums) { int mi = 1e6, mx = -1e6; for (int num : nums) { mi = min(mi, num); mx = max(mx, num); } int ans = 0; for (int num : nums) if (mi < num && num < mx) ++ans; return ans; }};class Solution: def countElements(self, nums: List[int]) -> int: mi, mx = min(nums), max(nums) return sum(mi < num < mx for num in nums)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.