The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Problem

Given an integer array nums, return the number of elements that have both a strictly smaller and a strictly greater element appearance in nums. Do it in O(n) time.

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 appearance 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 appearance in nums.

Constraints:

    1 <= nums.length <= 100    //length of array
    -105 <= nums[i] <= 105

Interpretation of the Problem

The problem can be interpreted as follows: Count the number of elements that are greater than the smallest element and less than the greatest element. There can be more than one of the same smallest element, and there can be more than one of the same greatest element.

Note

The solution to this problem does not really need frequency-of-occurrences array. However, it involves counting, so it is still part of the chapter.

Brute Force Approach

The naive or brute-force-approach involves considering each element and iterating over the whole array to know if there is any element smaller or greater than it. That takes at least O(n²) time. The student has been asked to solve the problem in O(n) time. So the brute-force approach is not addressed any further.

O(n) Approach

The given array has to be iterated all over, two times. In the first scan, the minimum and maximum values in the array are obtained. In the second scan, any number that is greater than the minimum value and less than the maximum value, is counted.

One of the constraints given in the problem description is:

    -100,000 <= nums[i] <= +100,000

So, at the start of the algorithm, the smallest number for comparison is considered as -100,001 (not -100,000) and the biggest number for comparison is considered as +100,001 (not +100,000). At the start, the counter for the number of elements in-between the smallest and biggest numbers, is set to 0.

The O(n) Program

The program is (read through the code and comments):

#include <stdio.h>

int countInBtwn(int A[], int n, int low, int high) {  
    int max = low;    //new max has to be greatest
    int min = high;    //new min has to be least
    
    int counter = 0;

    for (int i=0; i < n; i++) {
        if (A[i] < min)
            min = A[i];    //new min
        if (A[i] > max)
            max = A[i];    //new max
    }
    for (int i=0; i < n; i++) {
        if (min < A[i] && A[i] < max) 
            counter = counter + 1;
    }
    
    return counter;
}

int main(int argc, char **argv) 
{   
    int low = -100001;    //each element is greater than low
    int high = +100001;    //each element is less than high

    int A1[] = {11, 7, 2, 15};
    int n1 = sizeof(A1) / sizeof(A1[0]);    //length of given array
    int ret1 = countInBtwn(A1, n1, low, high);
    printf("%i\n", ret1);
    
    int A2[] = {-3, 3, 3, 90};
    int n2 = sizeof(A2) / sizeof(A2[0]);    //length of given array
    int ret2 = countInBtwn(A2, n2, low, high);
    printf("%i\n", ret2);
    
    int A3[] = {4, 4, 4, 4, 4};
    int n3 = sizeof(A3) / sizeof(A3[0]);    //length of given array
    int ret3 = countInBtwn(A3, n3, low, high);
    printf("%i\n", ret3);
    
    int A4[] = {6, 6, 6, 9, 9, 9};
    int n4 = sizeof(A4) / sizeof(A4[0]);    //length of given array
    int ret4 = countInBtwn(A4, n4, low, high);
    printf("%i\n", ret4);

    return 0;
}

The output is:

    2
    2
    0
    0

as expected.

The time complexity for the called function is actually O(2n) for the two for-loops. However, the coefficient (multiplicand of 2) is usually omitted to give a time complexity of O(n). If the time to assign the elements to the given array is taken into consideration, the the time complexity for the whole program would actually be O(3n). Ignoring the 3 still gives O(n).

The space complexity for the whole program is O(n), referring to the array in the calling function area. This is the same array in the called function. The O(1) space for the maximum and minimum values are ignored (negligible).

Thanks for reading.