algoadvance

Leetcode 2733. Neither Minimum nor Maximum

Problem Statement

Given an integer array nums containing distinct positive integers, we need to return any number from the array that is neither the minimum value nor the maximum value in the array. If there are no such numbers, we should return -1.

The constraints are:

Clarifying Questions

  1. What should we return if the array has only one or two elements?
    • Return -1 since it is not possible to have an element that is neither the minimum nor the maximum.
  2. Are the elements in the array guaranteed to be distinct?
    • Yes, all array elements are distinct.

Strategy

  1. Identify Edge Cases: If the length of the array is less than 3, return -1.
  2. Find Minimum and Maximum: Traverse the array to find the minimum and maximum values.
  3. Pick an Element: Iterate through the array again to find and return any element that is neither the minimum nor the maximum.

Code

Here’s a possible implementation in C++:

#include <iostream>
#include <vector>
#include <algorithm> // For std::min_element and std::max_element

int neitherMinNorMax(const std::vector<int>& nums) {
    if (nums.size() < 3) {
        return -1; // Not enough elements to satisfy the condition
    }
    
    // Find the minimum and maximum elements in the array
    int minElem = *std::min_element(nums.begin(), nums.end());
    int maxElem = *std::max_element(nums.begin(), nums.end());
    
    // Find any element that is neither the minimum nor the maximum
    for (const int& num : nums) {
        if (num != minElem && num != maxElem) {
            return num;
        }
    }
    
    // If every element is either the minimum or the maximum (special case)
    return -1;
}

int main() {
    std::vector<int> nums = {3, 1, 2, 4};
    int result = neitherMinNorMax(nums);
    std::cout << "Result: " << result << std::endl;
    return 0;
}

Time Complexity

Thus, the overall time complexity is O(n), making the solution efficient given the constraints.

Space Complexity

The provided code effectively and efficiently finds an element that is neither the minimum nor the maximum from a given list of distinct positive integers.

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