#2148

Easy

LeetCode Problem Workspace

Count Elements With Strictly Smaller and Greater Elements

Count elements in an array that have both strictly smaller and strictly greater numbers using array sorting efficiently.

array sorting counting

Problem Statement

Given an integer array nums, determine the total number of elements that have both a strictly smaller element and a strictly greater element present in the array. Only exclude elements that are the minimum or maximum values.

For example, in nums = [11,7,2,15], elements 7 and 11 each have both a smaller and a larger number. Similarly, nums = [-3,3,3,90] contains two 3s that satisfy this condition. Return the total count of such elements.

Examples

Example 1

Input: nums = [11,7,2,15]

Output: 2

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

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

Solution Approach

Sort the array to identify bounds

Sorting nums allows quick access to the minimum and maximum elements. Once sorted, the first element is the minimum and the last is the maximum, which can be excluded from the count.

Count eligible elements

Iterate over the sorted array and count every element that is not equal to the minimum or maximum. This ensures each counted element has both strictly smaller and strictly greater elements.

Return the result

After scanning the array and counting all eligible elements, return the total count as the solution. This approach avoids nested loops and ensures linear counting after sorting.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to sorting, then O(n) for counting, giving overall O(n log n). Space complexity is O(1) extra if in-place sorting is used, or O(n) if a copy is made.

What Interviewers Usually Probe

The array length is small enough to consider sorting first.
They may hint at excluding only minimum and maximum elements.
Expect to discuss edge cases with duplicates of min or max.

Common Pitfalls or Variants

Common pitfalls

Counting minimum or maximum elements incorrectly.
Not handling duplicate values properly, especially when min or max repeats.
Using nested loops unnecessarily, increasing time complexity.

Follow-up variants

Count elements with at least k strictly smaller and greater elements.
Return indices instead of counts for elements with both smaller and greater values.
Apply the same pattern to a 2D matrix by flattening and counting elements.

FAQ

What does 'strictly smaller and greater elements' mean in this problem?

It means each counted element must have at least one other number smaller than it and at least one number larger than it in the array.

Can duplicates of the minimum or maximum be counted?

No, all instances of the minimum or maximum should be excluded, even if there are duplicates.

Is sorting necessary for this problem?

Sorting simplifies identifying the minimum and maximum elements, making counting straightforward and efficient.

How does this relate to the 'Array plus Sorting' pattern?

The pattern applies by using sorting to expose array bounds and then applying a simple linear scan for counting elements.

What if all elements are equal?

If all elements are the same, there are no elements with strictly smaller or greater numbers, so the count is zero.

terminal

Solution

Solution 1: Find Minimum and Maximum Values

According to the problem description, we can first find the minimum value $\textit{mi}$ and the maximum value $\textit{mx}$ of the array $\textit{nums}$. Then, traverse the array $\textit{nums}$ and count the number of elements that satisfy $\textit{mi} < x < \textit{mx}$.

1

2

3

4

class Solution:
    def countElements(self, nums: List[int]) -> int:
        mi, mx = min(nums), max(nums)
        return sum(mi < x < mx for x in nums)

Continue Practicing

#2225 find players with zero or one losses #2248 intersection of multiple arrays #1782 count pairs of nodes