algoadvance

Leetcode 2148. Count Elements With Strictly Smaller and Greater Elements

Problem Statement

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

Clarifying Questions

Before we start with the solution, let’s clarify a few points about the problem:

  1. Input Size: Is there any constraint on the size of the input array? (Typically, constraints would be provided, e.g., 1 <= nums.length <= 1000)
  2. Value Range: What is the range of integers in the array? (Usually, -10^5 <= nums[i] <= 10^5)
  3. Duplicates: Can the array contain duplicates? (Assume yes as no constraints are given)

Let’s move forward with the understanding that the array can have any length, the values can be any integer, and the array can contain duplicates.

Strategy

To solve this problem, we need to:

  1. Identify the minimum and maximum values in the array.
  2. Count how many elements there are such that they are strictly greater than the minimum value and strictly less than the maximum value.

Plan

  1. Find the minimum and maximum values in the array.
  2. Iterate through the array and count the elements that are strictly greater than the minimum and strictly smaller than the maximum.

Code

Here is the implementation in Java:

public class ElementCounter {

    public int countElements(int[] nums) {
        if (nums == null || nums.length < 3) {
            return 0;
        }
        
        int min = nums[0];
        int max = nums[0];
        
        // Find the min and max values in the array
        for (int num : nums) {
            if (num < min) {
                min = num;
            } else if (num > max) {
                max = num;
            }
        }
        
        int count = 0;
        // Count elements that are strictly greater than min and strictly less than max
        for (int num : nums) {
            if (num > min && num < max) {
                count++;
            }
        }
        
        return count;
    }

    public static void main(String[] args) {
        ElementCounter counter = new ElementCounter();
        int[] nums = {11, 7, 2, 15}; // Example input
        System.out.println(counter.countElements(nums)); // Expected output: 2
    }
}

Time Complexity

  1. Finding minimum and maximum values requires a single pass through the array: O(n)
  2. Counting the elements that fit the criteria also requires a single pass through the array: O(n)

Overall, the time complexity of this solution is O(n), where n is the number of elements in the input array. This is efficient and expected for this type of problem.

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