# Count Elements With Strictly Smaller and Greater Elements 
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-elements-with-strictly-smaller-and-greater-elements)
Canonical: https://scaleengineer.com/dsa/problems/count-elements-with-strictly-smaller-and-greater-elements
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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`

# Approaches
## Brute Force with Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Sorting the Array
A more efficient approach is to first sort the array. Once sorted, an element has a strictly smaller and a strictly greater element if and only if it is not the minimum or maximum value in the array. This is because the smallest element in the sorted array will be a candidate for the 'strictly smaller' element, and the largest for the 'strictly greater' one.
**Time:** O(n log n), which is dominated by the sorting step. The subsequent scan of the array takes O(n) time. · **Space:** O(log n) to O(n), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitives has an average space complexity of O(log n) for the recursion stack.
**Pros:** Significantly faster than the brute-force approach for larger arrays.; The logic after sorting is very straightforward.
**Cons:** The sorting step can be overkill, as a linear time solution exists.; It might modify the input array, which could be undesirable in some contexts. A copy would use O(n) space.
### Explanation
The core idea is that after sorting, the minimum element will be at the beginning of the array (`nums[0]`) and the maximum element will be at the end (`nums[n-1]`). Any element `x` that satisfies the condition `min(nums) < x < max(nums)` will have a strictly smaller element (the array's minimum) and a strictly greater element (the array's maximum). So, we first sort the array. Then, we find the minimum and maximum values. Finally, we iterate through the array and count how many elements fall strictly between these two values.

```java
import java.util.Arrays;

class Solution {
    public int countElements(int[] nums) {
        if (nums.length < 3) {
            return 0;
        }
        Arrays.sort(nums);
        int minVal = nums[0];
        int maxVal = nums[nums.length - 1];
        int count = 0;
        // We can skip the first and last elements as they can't be between min and max.
        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] > minVal && nums[i] < maxVal) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
*   Sort the input array `nums` in non-decreasing order.
*   If the array has fewer than 3 elements, it's impossible to satisfy the condition, so return 0.
*   Identify the minimum value (`minVal = nums[0]`) and the maximum value (`maxVal = nums[n-1]`).
*   Initialize a counter `count` to zero.
*   Iterate through the sorted array. For each element `num`, check if it is strictly greater than `minVal` and strictly less than `maxVal`.
*   If `num > minVal` and `num < maxVal`, increment the `count`.
*   Return the final `count`.

## Linear Scan to Find Min and Max
The most efficient approach involves realizing that we only need to count the elements that are not the minimum and not the maximum value in the array. This can be achieved in linear time by first finding the minimum and maximum elements and then counting the numbers that fall between them.
**Time:** O(n). We perform two passes over the array, each taking O(n) time. Thus, the total time complexity is O(n) + O(n) = O(n). · **Space:** O(1). We only use a few variables to store the min, max, and count, regardless of the input size.
**Pros:** Optimal time complexity of O(n).; Optimal space complexity of O(1).; Does not require modifying the input array.
**Cons:** Requires two passes over the data, though this is a minor drawback given the overall linear time complexity.
### Explanation
An element `x` has a strictly smaller and a strictly greater element if and only if `x` is not the global minimum and not the global maximum of the array. If `x` is not the minimum, then the global minimum is strictly smaller than `x`. If `x` is not the maximum, then the global maximum is strictly greater than `x`. This simplifies the problem to: 1. Find the minimum and maximum values in the array. 2. Count how many elements are strictly between this minimum and maximum. This can be implemented in two passes over the array.

```java
class Solution {
    public int countElements(int[] nums) {
        if (nums.length < 3) {
            return 0;
        }
        
        int minVal = Integer.MAX_VALUE;
        int maxVal = Integer.MIN_VALUE;
        
        // First pass: find min and max
        for (int num : nums) {
            minVal = Math.min(minVal, num);
            maxVal = Math.max(maxVal, num);
        }
        
        // If all elements are the same, no element can satisfy the condition
        if (minVal == maxVal) {
            return 0;
        }
        
        int count = 0;
        // Second pass: count elements between min and max
        for (int num : nums) {
            if (num > minVal && num < maxVal) {
                count++;
            }
        }
        
        return count;
    }
}
```
### Algorithm
*   Find the minimum element `minVal` and maximum element `maxVal` in `nums` by iterating through the array once.
*   Initialize `count = 0`.
*   Iterate through `nums` a second time.
*   For each element `num`, if `num > minVal` and `num < maxVal`, increment `count`.
*   Return `count`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  int countElements(vector<int> &nums) {
    int mi = 1e6, mx = -1e6;
    for (int num : nums) {
      mi = min(mi, num);
      mx = max(mx, num);
    }
    int ans = 0;
    for (int num : nums)
      if (mi < num && num < mx)
        ++ans;
    return ans;
  }
};

```

### Python

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

```