2148. Count Elements With Strictly Smaller and Greater Elements

EasyArraySorting
Leetcode Link

Problem Description

The goal of the problem is to count how many elements in an integer array nums have at least one other element in the array that is strictly smaller and at least one other element that is strictly greater. In other words, for an element to be counted, it cannot be the smallest or the largest element in the array. The task is to find the number of such elements.

Intuition

To solve this problem efficiently, what comes to mind is that if we know the smallest and the largest elements of the array, we can simply iterate through the array and count the elements that fall strictly between these two extremes. That is because the elements that are equal to the minimum or maximum can't possibly satisfy the condition of having both a strictly smaller and a strictly greater element in the array.

Thus, the solution involves the following steps:

  1. Find the minimum value in nums, denoted as mi.
  2. Find the maximum value in nums, denoted as mx.
  3. Iterate through each element num in nums and
    • Increment a counter each time mi < num < mx is True.
  4. The counter value gives us the desired number of elements.

In the provided solution, a simple yet elegant approach is taken where Python's built-in min and max functions are used to find mi and mx. Then a generator expression is used within the sum function to add up all the boolean values that are True for elements that fall strictly between the minimum and maximum, which inherently gives us the count.

Learn more about Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Solution Approach

The implementation of the solution is straightforward and leverages Python's concise and powerful syntax. We use two built-in functions and a very common Python pattern, list comprehension with a condition (which, in this context, creates a generator expression).

Here's how the solution is implemented:

  1. Finding the Minimum and Maximum: We begin by finding the minimum and maximum value within the nums list using Python's min and max functions.

    1mi, mx = min(nums), max(nums)

    This step is done in constant time with respect to the input array size, assuming the min and max functions are implemented efficiently (which they are in Python).

  2. Counting the Elements: We then count the elements that are strictly greater than mi and strictly less than mx using a generator expression within the sum function.

    1return sum(mi < num < mx for num in nums)

    The expression mi < num < mx evaluates to True if num lies strictly between mi and mx. In Python, when True is passed to the sum function, it is treated as 1, and False is treated as 0. Thus we effectively count the number of True cases which correspond to valid elements.

    This step has a time complexity of O(n), where n is the size of the input list, because it involves iterating over all the elements in the list once.

The solution does not explicitly use any additional data structures, relying on Python's list and integer types. The pattern used here is commonly referred to as a comprehension. It's a concise way to create a new list or in this case, generate values on the fly for the sum function, while applying a condition or mapping each item to a new value.

This two-step approach is very efficient because it minimizes the amount of work needed to be done on the input array. By first determining the bounds with min and max, and then using a simple linear scan with a generator expression to count the qualifying elements, we arrive at an elegant and efficient solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Example Walkthrough

Let's suppose our input nums array is [3, 7, 2, 5, 6].

  1. The first step is finding the minimum (mi) and maximum (mx) value in the array. We use the min() and max() functions of Python.

    • mi = min(nums) would evaluate to 2.
    • mx = max(nums) would evaluate to 7.

  2. The second step involves iterating over the array and counting the elements that are strictly greater than the minimum (2) and strictly less than the maximum (7).

    • The first element, 3, is greater than 2 and less than 7, so it meets the condition.
    • The second element, 7, is equal to mx and hence does not meet the condition.
    • The third element, 2, is equal to mi and also does not meet the condition.
    • The fourth element, 5, meets the condition as it is greater than 2 and less than 7.
    • The fifth element, 6, also meets the condition.

  3. Counting the elements that passed the condition:

    • We calculate sum(mi < num < mx for num in nums), which is essentially sum([True, False, False, True, True]).
    • This is equivalent to 1 + 0 + 0 + 1 + 1, which sums up to 3.

Thus, for the array [3, 7, 2, 5, 6], the function would return 3, indicating there are three elements within the array that have at least one other element in the array strictly smaller and at least one strictly greater.

Solution Implementation

1class Solution:
2    def countElements(self, nums: List[int]) -> int:
3        # Find the minimum and maximum values in the list of numbers
4        min_val, max_val = min(nums), max(nums)
5      
6        # Count and return the number of elements that are strictly between the minimum
7        # and maximum values using a generator expression within the sum function.
8        return sum(min_val < num < max_val for num in nums)
9
1class Solution {
2    public int countElements(int[] nums) {
3        // Initialize the minimum and maximum values possible for the elements in the array.
4        int minElement = Integer.MAX_VALUE, maxElement = Integer.MIN_VALUE;
5
6        // Iterate over each element to find the smallest and largest number.
7        for (int num : nums) {
8            minElement = Math.min(minElement, num);
9            maxElement = Math.max(maxElement, num);
10        }
11
12        // Initialize the counter for the number of elements that fall strictly between the min and max.
13        int count = 0;
14
15        // Count elements that are strictly greater than the minimum and strictly less than the maximum.
16        for (int num : nums) {
17            if (minElement < num && num < maxElement) {
18                count++;
19            }
20        }
21
22        // Return the total count of elements satisfying the condition.
23        return count;
24    }
25}
26
1class Solution {
2public:
3    // Function to count the elements that are greater than the minimum
4    // and less than the maximum elements in the given vector nums
5    int countElements(vector<int>& nums) {
6        // Initialize minimum and maximum values with extremes
7        int minVal = INT_MAX; // Use INT_MAX to represent initially the largest possible integer
8        int maxVal = INT_MIN; // Use INT_MIN to represent initially the smallest possible integer
9      
10        // Loop to find the smallest and largest values in the vector
11        for (int num : nums) {
12            minVal = std::min(minVal, num); // Update minVal to the minimum found so far
13            maxVal = std::max(maxVal, num); // Update maxVal to the maximum found so far
14        }
15      
16        // Initialize the answer count
17        int ans = 0;
18      
19        // Iterate through the elements of nums
20        for (int num : nums) {
21            // Increment ans if num is greater than minVal and less than maxVal
22            if (minVal < num && num < maxVal)
23                ans++;
24        }
25      
26        // Return the count of elements that satisfy the condition
27        return ans;
28    }
29};
30
1function countElements(nums: number[]): number {
2    // Find the minimum and maximum elements in the array.
3    const minValue = Math.min(...nums),
4          maxValue = Math.max(...nums);
5  
6    // Initialize the count of elements that are not the min or max value.
7    let count = 0;
8
9    // Iterate through the array to count elements that are greater than min and less than max.
10    for (let i = 0; i < nums.length; ++i) {
11        const currentElement = nums[i];
12        if (currentElement < maxValue && currentElement > minValue) {
13            // Increment the count for each qualifying element.
14            count++;
15        }
16    }
17
18    // Return the total count of elements that are not the min or max value.
19    return count;
20}
21
Not Sure What to Study? Take the 2-min Quiz：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Time and Space Complexity

The time complexity of the code is O(n), where n is the number of elements in the input list nums. This is because the min(nums) and max(nums) functions each iterate through the list once, resulting in 2 * O(n) operations, which simplifies to O(n) in Big O notation. The sum function with the generator expression also iterates through the list once, adding another O(n) operation. Therefore, the overall time complexity remains O(n).

The space complexity of the code is O(1). The reason behind this is that only a constant amount of additional space is used. Variables mi and mx are used to store the minimum and maximum elements of the list, which does not depend on the size of the input list. The generator expression in the sum function computes its result in-place and does not allocate additional space that is dependent on the input size. Thus, the space used is constant regardless of n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

A heap is a ...?

Recommended Readings

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫