What is the time complexity of the Brute Force approach?

The time complexity of the Brute Force approach is O(n²), where n is the number of elements in the array.

What is the most efficient approach to solve this problem?

The Single Pass (Min/Max) approach is the most efficient, with a time complexity of O(n) and space complexity of O(1).

How does the Sorting approach work?

The Sorting approach sorts the array and then subtracts the count of the minimum elements and maximum elements from the total length. It has a time complexity of O(n log n).

Count Elements With Strictly Smaller and Greater Elements

Difficulty: Easy | Acceptance: 60.00% | Paid: No Topics: Array, Sorting, Counting

Given an array nums, return the number of elements x such that there exists a strictly smaller element and a strictly greater element in the array.

Examples
Constraints
Approach 1: Brute Force
Approach 2: Single Pass (Min/Max)
Approach 3: Sorting

Examples

Example 1:

Input: nums = [11,7,2,15]
Output: 2
Explanation: The element 7 has a strictly smaller element (2) and a strictly greater element (11).
The element 11 has a strictly smaller element (7) and a strictly greater element (15).

Example 2:

Input: nums = [-3,-3,-3]
Output: 0
Explanation: There is no strictly smaller or strictly greater element for any element.

Constraints

2 <= nums.length <= 100
-10^5 <= nums[i] <= 10^5

Approach 1: Brute Force

Intuition For every element in the array, we explicitly check if there exists any other element that is strictly smaller and any other element that is strictly greater.

Steps

Initialize a result counter to 0.
Iterate through each element x in the array.
For each x, iterate through the array again to find if there is a y such that y < x and a z such that z > x.
If both conditions are met, increment the counter.
Return the counter.

python

Complexity

Time: O(n²)
Space: O(1)
Notes: Simple to implement but inefficient for large arrays.

Approach 2: Single Pass (Min/Max)

Intuition An element x is valid if it is strictly greater than the minimum value of the array and strictly less than the maximum value of the array. We can find the global min and max in one pass, then count elements satisfying the condition.

Steps

Find the minimum value mn and maximum value mx in the array.
Iterate through the array and count how many elements x satisfy mn < x < mx.
Return the count.

python

Complexity

Time: O(n)
Space: O(1)
Notes: Optimal solution with linear time complexity.

Approach 3: Sorting

Intuition If we sort the array, all elements strictly between the first element (minimum) and the last element (maximum) are valid. We just need to exclude the occurrences of the minimum and maximum values.

Steps

Sort the array in non-decreasing order.
If the first element equals the last element, return 0 (all elements are the same).
Otherwise, count the number of elements equal to the first element (min_count) and the number of elements equal to the last element (max_count).
The result is total_length - min_count - max_count.

python

Complexity

Time: O(n log n)
Space: O(1) or O(n) depending on the sorting algorithm implementation.
Notes: Sorting adds overhead compared to the linear approach, but is conceptually straightforward.