Problem Statement
Given a non-empty integer array nums, return the minimum element present in the array.
Example 1
Input: nums = [2, 5, 1, 9, 3]
Output: 1
Explanation: Among all elements, 1 is the smallest value.
Example 2
Input: nums = [-4, -1, -9, -2]
Output: -9
Explanation: Among all negative numbers, -9 is the smallest value.
Brute Force Approach
Sorting the values in non-decreasing order places the smallest element at the first position.
A copy of the input array is sorted so that the original arrangement remains unchanged. The first value of the sorted copy is then returned.
Algorithm
Create
sortedNumsas a copy ofnumsso that sorting does not change the original array.Sort
sortedNumsin non-decreasing order, which brings the smallest value to the first position.Return
sortedNums[0], since the first element after sorting is the minimum value.
Dry Run
Minimum Element in Array Brute Force Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: int smallestElement(const vector<int>& nums) { // Sort a copy to preserve the original array. vector<int> sortedNums = nums; sort(sortedNums.begin(), sortedNums.end()); // The first position contains the smallest value after sorting. return sortedNums[0]; }};int main() { vector<int> nums = {5, 2, 9, 1}; Solution solution; cout << "Minimum element: " << solution.smallestElement(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N log N), where N represents the number of elements. Sorting the copied array requires O(N log N) time.
Space Complexity: O(N), because a separate array of size N is created to preserve the original input. The sorting method may also use implementation-dependent internal memory.
Optimal Approach
Sorting the complete array is unnecessary when only the smallest value is required.
Maintain the smallest value found so far while traversing the array. Whenever a smaller value appears, replace the stored candidate with that value.
After every element has been examined, the stored candidate is the minimum element.
Algorithm
Initialize
minElementwithnums[0], giving us a valid array element as the first minimum candidate. This avoids incorrect results when all values are positive or negative.Start traversing from index
1, since the first element has already been considered while initializingminElement.Compare each current element with
minElementto check whether a smaller value has been found.If the current element is smaller, update
minElementso it always holds the smallest value seen so far.Return
minElementafter the traversal, as every element has been checked.
Dry Run
Minimum Element in Array Optimal Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: int smallestElement(const vector<int>& nums) { // The first element provides the initial valid candidate. int minElement = nums[0]; // Compare every remaining value with the smallest found so far. for (int index = 1; index < nums.size(); index++) { if (nums[index] < minElement) { minElement = nums[index]; } } return minElement; }};int main() { vector<int> nums = {5, 2, 9, 1}; Solution solution; cout << "Minimum element: " << solution.smallestElement(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), where N represents the number of elements. Every element is examined once.
Space Complexity: O(1), because only minElement requires auxiliary storage.
Interview follow-up Questions
If every element is positive, initializing minElement with 0 would incorrectly return 0 even when it is not present in the array. Using nums[0] guarantees that the initial minimum is a valid array element.
Be the first to add a comment.