algoadvance

Leetcode 2148. Count Elements With Strictly Smaller and Greater Elements

Problem Statement

Given an integer array nums, return the number of elements that have both a strictly smaller and a strictly greater element.

Clarifying Questions

  1. Negative Numbers: Can nums contain negative numbers?
    • Yes, nums can contain both positive and negative integers.
  2. Duplicate Numbers: Is it possible for nums to contain duplicates?
    • Yes, nums can have duplicate values.
  3. Minimum Number of Elements: What is the minimum length nums can have?
    • The array can have a minimum of 1 element. However, to have both a strictly smaller and a strictly greater element, the array must contain at least 3 elements.

Strategy

  1. Sort the Array: First, sort the array to easily find the smallest and largest elements.
  2. Identify Boundaries: Identify the smallest and largest elements in the sorted array (first and last elements respectively).
  3. Count Valid Elements: Traverse the array and count elements that are strictly greater than the smallest element and strictly less than the largest element.

Code

Here’s the C++ implementation:

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int countElements(vector<int>& nums) {
    if (nums.size() < 3) return 0; // If less than 3 elements, not possible to have both smaller and greater elements
    
    sort(nums.begin(), nums.end()); // Sort the array
    int smallest = nums.front(); // Smallest element
    int largest = nums.back(); // Largest element
    
    int count = 0;

    // Count elements strictly between smallest and largest
    for (int num : nums) {
        if (num > smallest && num < largest) {
            ++count;
        }
    }

    return count;
}

int main() {
    vector<int> nums = {11, 7, 2, 15};
    cout << "Count of elements with both strictly smaller and greater elements: " << countElements(nums) << endl;

    return 0;
}

Time Complexity

  1. Sorting the Array: The sorting operation takes (O(n \log n)).
  2. Traversing the Array: The traversal operation takes (O(n)).

Thus, the overall time complexity is (O(n \log n)) where (n) is the number of elements in the array.

Space Complexity

The space complexity is (O(1)) if we disregard the space used by the sorting function (which typically uses (O(\log n)) space). Therefore, the main space usage is constant, independent of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI