Leetcode 2733: Neither Minimum nor Maximum
You are given an array
nums containing distinct positive integers. Your task is to find and return any number from the array that is neither the smallest nor the largest number, or return -1 if no such number exists.Problem
Approach
Steps
Complexity
Input: The input consists of a single array `nums` of integers.
Example: nums = [4, 2, 1, 3]
Constraints:
• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• All values in nums are distinct.
Output: Return any integer from the array that is neither the minimum nor the maximum value, or return -1 if no such number exists.
Example: Output: 2
Constraints:
Goal: The goal is to find an integer from the array that is neither the smallest nor the largest number.
Steps:
• Check if the array has less than 3 elements. If true, return -1.
• Find the minimum and maximum values in the array.
• Loop through the array and return any number that is not the minimum or maximum.
Goal: The length of the array and the range of the integers in the array.
Steps:
• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• All values in nums are distinct.
Assumptions:
• All integers in the array are distinct.
• The array length is at least 2.
• Input: nums = [4, 2, 1, 3]
• Explanation: In this example, the minimum value is 1 and the maximum value is 4. Therefore, 2 or 3 can be valid answers.
• Input: nums = [1, 2]
• Explanation: Since the array has only two elements, no element is both non-minimal and non-maximal. Therefore, the output is -1.
Approach: The problem is solved by finding the minimum and maximum values, then checking for any element that lies between them.
Observations:
• We can solve the problem by simply finding the min and max values in the array.
• The problem is straightforward with a time complexity of O(n).
• If the array has less than 3 elements, return -1 immediately.
Steps:
• Find the minimum and maximum values in the array.
• Check if the array has more than 2 elements.
• If true, return any element that is between the min and max values, otherwise return -1.
Empty Inputs:
• The array has less than 3 elements.
Large Inputs:
• Consider testing with arrays of size 100.
Special Values:
• The array has only two distinct values.
Constraints:
• All values are distinct, so the result is deterministic.
int findNonMinOrMax(vector<int>& A) {
if (A.size() < 3)
return -1;
int mx = max(A[0], max(A[1], A[2])), mn = min(A[0], min(A[1], A[2]));
for (int i = 0; i < 3; ++i)
if (mn < A[i] && A[i] < mx)
return A[i];
return -1;
}
1 : Function Definition
int findNonMinOrMax(vector<int>& A) {
The function `findNonMinOrMax` is defined to take a reference to a vector of integers `A` as input and return an integer.
2 : Condition Check
if (A.size() < 3)
The function checks if the size of the vector `A` is less than 3. If true, it returns -1 as a result, since it requires at least 3 elements to find a non-minimum and non-maximum value.
3 : Return Statement
return -1;
If the size of the vector `A` is less than 3, the function immediately returns -1.
4 : Variable Initialization
int mx = max(A[0], max(A[1], A[2])), mn = min(A[0], min(A[1], A[2]));
The variables `mx` and `mn` are initialized to store the maximum and minimum values among the first three elements of the vector `A`.
5 : Loop Start
for (int i = 0; i < 3; ++i)
A for-loop is initiated to iterate over the first three elements of the vector `A`.
6 : Conditional Check
if (mn < A[i] && A[i] < mx)
Inside the loop, the function checks if the current element `A[i]` is greater than the minimum value `mn` and less than the maximum value `mx`. If true, this element is returned as the result.
7 : Return Statement
return A[i];
If the current element satisfies the condition of being neither the minimum nor the maximum, it is returned as the result.
8 : Return Statement
return -1;
If no element satisfies the condition within the loop, the function returns -1, indicating no such element exists.
Best Case: O(1) when there are only two elements.
Average Case: O(n) where n is the number of elements in the array.
Worst Case: O(n) because we need to find the minimum and maximum of the array.
Description: Finding the minimum and maximum takes linear time.
Best Case: O(1) when the array has minimal elements.
Worst Case: O(1) because we only store a few extra variables.
Description: The space complexity is constant as no additional space is required.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus