Scale Engineer

Count Elements With Strictly Smaller and Greater Elements

Easy
#1957Time: 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.
Patterns
Counting
Algorithms
Sorting
Data structures
Array

Prompt

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:

nums

Example 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 count to zero.
  • Loop through the array with an outer loop, picking one element currentElement at a time.
  • For each currentElement, use an inner loop to iterate through the entire array again.
  • Inside the inner loop, maintain two boolean flags: foundSmaller and foundGreater, both initially false.
  • Compare currentElement with every other element otherElement in the array.
  • If otherElement < currentElement, set foundSmaller to true.
  • If otherElement > currentElement, set foundGreater to true.
  • If after the inner loop completes, both foundSmaller and foundGreater are true, it means currentElement satisfies the condition. Increment the count.
  • After the outer loop finishes, count will 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.

Solutions

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;  }}

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.

← Previous

Previous problem

Next →

Next problem