Count Elements With Strictly Smaller and Greater Elements solution and explanation
Google
9 more videos on this problem
Count Elements With Strictly Smaller and Greater Elements | Leetcode 2148 | Weekly Contest 277|JavaPepcoding · 5:33 · 3K views
Count Elements With Strictly Smaller and Greater Elements| Leetcode 2148 | Contest 277| 2 ApproachesCoding Decoded · 6:54 · 809 views
2148 Count Elements With Strictly Smaller and Greater Elements || Weekly Contest 277 || EasyBro Coders · 3:01 · 733 views
2148. Count Elements With Strictly Smaller and Greater Elements(Leetcode Problem):Weekly Contest 277viralSongs · 2:41 · 295 views
2148. Count Elements With Strictly Smaller and Greater Elements (Leetcode Easy)Programming Live with Larry · 3:04 · 287 views
LeetCode 2148 : Count Elements With Strictly Smaller and Greater Elements || EASY || JAVA ||SolutionCodeGPT · 10:42 · 132 views
Count Elements With Strictly Smaller and Greater Elements - LeetCode 2148 - Java Solutionalgobest - Computer Science · 1:50 · 83 views
LeetCode 2148 - Count Elements With Strictly Smaller and Greater Elements - JavaScript - [EASY]NoviceJS · 8:54 · 78 views
2148. Count Elements With Strictly Smaller and Greater Elements with python | Leetcode with pythonArsalan Ahmed · 4:25 · 55 views
2148 |Count Elements With Strictly Smaller and Greater Elements | Leetcode| Contest 277Ashutosh sharma · 7:10 · 55 views
The problem
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.
def count_elements(nums):
nums.sort()
min_val = nums[0]
max_val = nums[-1]
count = 0
for num in nums:
if num > min_val and num < max_val:
count += 1
return count
# Example usage
nums1 = [11, 7, 2, 15]
print(count_elements(nums1)) # Output: 2
nums2 = [-3, 3, 3, 90]
print(count_elements(nums2)) # Output: 2import java.util.Arrays;
public class CountElements {
public static int countElements(int[] nums) {
Arrays.sort(nums);
int minVal = nums[0];
int maxVal = nums[nums.length - 1];
int count = 0;
for (int num : nums) {
if (num > minVal && num < maxVal) {
count++;
}
}
return count;
}
public static void main(String[] args) {
int[] nums1 = {11, 7, 2, 15};
System.out.println(countElements(nums1)); // Output: 2
int[] nums2 = {-3, 3, 3, 90};
System.out.println(countElements(nums2)); // Output: 2
}
}function countElements(nums) {
nums.sort((a, b) => a - b);
const minVal = nums[0];
const maxVal = nums[nums.length - 1];
let count = 0;
for (let num of nums) {
if (num > minVal && num < maxVal) {
count++;
}
}
return count;
}
// Example usage
const nums1 = [11, 7, 2, 15];
console.log(countElements(nums1)); // Output: 2
const nums2 = [-3, 3, 3, 90];
console.log(countElements(nums2)); // Output: 2#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int countElements(int *nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
int minVal = nums[0];
int maxVal = nums[numsSize - 1];
int count = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] > minVal && nums[i] < maxVal) {
count++;
}
}
return count;
}
int main() {
int nums1[] = {11, 7, 2, 15};
int size1 = sizeof(nums1) / sizeof(nums1[0]);
printf("%d\n", countElements(nums1, size1)); // Output: 2
int nums2[] = {-3, 3, 3, 90};
int size2 = sizeof(nums2) / sizeof(nums2[0]);
printf("%d\n", countElements(nums2, size2)); // Output: 2
return 0;
}using System;
class CountElements {
public static int CountElements(int[] nums) {
Array.Sort(nums);
int minVal = nums[0];
int maxVal = nums[nums.Length - 1];
int count = 0;
foreach (int num in nums) {
if (num > minVal && num < maxVal) {
count++;
}
}
return count;
}
static void Main() {
int[] nums1 = {11, 7, 2, 15};
Console.WriteLine(CountElements(nums1)); // Output: 2
int[] nums2 = {-3, 3, 3, 90};
Console.WriteLine(CountElements(nums2)); // Output: 2
}
}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.
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.
def count_elements(nums):
if len(nums) <= 2:
return 0
min_val, max_val = float('inf'), float('-inf')
for num in nums:
if num < min_val:
min_val = num
if num > max_val:
max_val = num
count = 0
for num in nums:
if num > min_val and num < max_val:
count += 1
return count
# Example usage:
nums1 = [11, 7, 2, 15]
print(count_elements(nums1)) # Output: 2
nums2 = [-3, 3, 3, 90]
print(count_elements(nums2)) # Output: 2public class CountElementsTwoPass {
public static int countElements(int[] nums) {
if (nums.length <= 2) {
return 0;
}
int minVal = Integer.MAX_VALUE;
int maxVal = Integer.MIN_VALUE;
for (int num : nums) {
if (num < minVal) {
minVal = num;
}
if (num > maxVal) {
maxVal = num;
}
}
int count = 0;
for (int num : nums) {
if (num > minVal && num < maxVal) {
count++;
}
}
return count;
}
public static void main(String[] args) {
int[] nums1 = {11, 7, 2, 15};
System.out.println(countElements(nums1)); // Output: 2
int[] nums2 = {-3, 3, 3, 90};
System.out.println(countElements(nums2)); // Output: 2
}
}function countElements(nums) {
if (nums.length <= 2) {
return 0;
}
let minVal = Infinity;
let maxVal = -Infinity;
for (let num of nums) {
if (num < minVal) {
minVal = num;
}
if (num > maxVal) {
maxVal = num;
}
}
let count = 0;
for (let num of nums) {
if (num > minVal && num < maxVal) {
count++;
}
}
return count;
}
// Example usage
const nums1 = [11, 7, 2, 15];
console.log(countElements(nums1)); // Output: 2
const nums2 = [-3, 3, 3, 90];
console.log(countElements(nums2)); // Output: 2#include <stdio.h>
#include <limits.h>
int countElements(int* nums, int numsSize) {
if (numsSize <= 2) return 0;
int minVal = INT_MAX;
int maxVal = INT_MIN;
for (int i = 0; i < numsSize; i++) {
if (nums[i] < minVal) {
minVal = nums[i];
}
if (nums[i] > maxVal) {
maxVal = nums[i];
}
}
int count = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] > minVal && nums[i] < maxVal) {
count++;
}
}
return count;
}
int main() {
int nums1[] = {11, 7, 2, 15};
int size1 = sizeof(nums1) / sizeof(nums1[0]);
printf("%d\n", countElements(nums1, size1)); // Output: 2
int nums2[] = {-3, 3, 3, 90};
int size2 = sizeof(nums2) / sizeof(nums2[0]);
printf("%d\n", countElements(nums2, size2)); // Output: 2
return 0;
}using System;
class CountElementsTwoPass {
public static int CountElements(int[] nums) {
if (nums.Length <= 2) {
return 0;
}
int minVal = Int32.MaxValue;
int maxVal = Int32.MinValue;
foreach (int num in nums) {
if (num < minVal) {
minVal = num;
}
if (num > maxVal) {
maxVal = num;
}
}
int count = 0;
foreach (int num in nums) {
if (num > minVal && num < maxVal) {
count++;
}
}
return count;
}
static void Main() {
int[] nums1 = {11, 7, 2, 15};
Console.WriteLine(CountElements(nums1)); // Output: 2
int[] nums2 = {-3, 3, 3, 90};
Console.WriteLine(CountElements(nums2)); // Output: 2
}
}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.
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).
class Solution {
public:
int countElements(vector<int>& nums) {
auto [mi, mx] = ranges::minmax_element(nums);
return ranges::count_if(nums, [mi, mx](int x) { return *mi < x && x < *mx; });
}
};function countElements(nums: number[]): number {
const mi = Math.min(...nums);
const mx = Math.max(...nums);
return nums.filter(x => mi < x && x < mx).length;
}func countElements(nums []int) (ans int) {
mi := slices.Min(nums)
mx := slices.Max(nums)
for _, x := range nums {
if mi < x && x < mx {
ans++
}
}
return
}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 | – |
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 |
Frequently asked questions
Is Count Elements With Strictly Smaller and Greater Elements easy or hard?
LeetCode classifies this problem as Easy. The key observation is that elements equal to the minimum or maximum cannot qualify. Once you recognize that, the solution reduces to a simple linear scan with constant space.
Count Elements With Strictly Smaller and Greater Elements Python/Java solution
The typical implementation scans the array to compute min and max, then performs a second loop counting elements strictly between them. This logic translates directly to Python, Java, JavaScript, C#, or C using simple comparisons and a counter variable.
How to solve Count Elements With Strictly Smaller and Greater Elements in O(n)?
Scan the array once to compute the minimum and maximum values. Then iterate again and count elements where value > min and value < max. Every such element automatically has both a smaller and a greater element in the array, giving an O(n) time and O(1) space solution.
Is Count Elements With Strictly Smaller and Greater Elements asked at Google/Amazon/Meta?
Problems of this pattern appear frequently in coding interviews at large tech companies because they test array traversal, edge-case reasoning, and optimization from sorting to linear scans. While the exact LeetCode ID may vary, similar min/max counting questions are common interview warmups.
What is the best approach for Count Elements With Strictly Smaller and Greater Elements ?
The optimal approach is a two-pass min/max scan. First find the global minimum and maximum values in O(n) time. Then count how many elements are strictly greater than the minimum and strictly less than the maximum. This works because only the extreme values fail the condition.
What data structure is used in Count Elements With Strictly Smaller and Greater Elements ?
The problem mainly uses a basic array with simple counting logic. The optimal solution only tracks two variables for the global minimum and maximum values while scanning the array. No additional data structures like hash maps or stacks are required.
What is the time complexity of Count Elements With Strictly Smaller and Greater Elements ?
The optimal solution runs in O(n) time with O(1) extra space. It performs one pass to compute the minimum and maximum values and another pass to count valid elements. A sorting-based alternative exists but costs O(n log n) time.