Count Elements With Strictly Smaller and Greater Elements

Easy
1121.

Count Elements With Strictly Smaller and Greater Elements

Count Elements With Strictly Smaller and Greater Elements is an easy coding problem on arrays, sorting and counting, asked in Amazon and Google interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var countElements = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    An element has something strictly smaller unless it is the minimum.

  2. Hint 2

    Likewise it has something strictly larger unless it is the maximum.

  3. 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

  1. Compute lo = min(nums) and hi = max(nums).
  2. Count the elements x with lo < 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 < hi handles 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