Problem Statement
Given a non-empty integer array nums, return its largest element.
Example 1
Input: nums = [2, 5, 1, 9, 3]
Output: 9
Explanation: Among all elements, 9 is the greatest value.
Example 2
Input: nums = [-4, -1, -9, -2]
Output: -1
Explanation: Among all negative numbers, -1 is the greatest value.
Brute Force Approach
Sorting the values in non-decreasing order places the largest element at the final position.
A copy of the input array is sorted so that the original arrangement remains unchanged. The final value of the sorted copy is then returned.
Algorithm
Create
sortedNumsas a copy ofnumsso the original ordering of the input remains unchanged.Sort
sortedNumsin non-decreasing order, which places the largest value at the last position.Return the last element of
sortedNums, since no element after sorting can be greater than it.
Dry Run
Maximum Element in Array Brute Force Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: int largestElement(const vector<int>& nums) { // Sort a copy to preserve the original arrangement. vector<int> sortedNums = nums; sort(sortedNums.begin(), sortedNums.end()); // The final position contains the largest value after sorting. return sortedNums.back(); }};int main() { vector<int> nums = {5, 2, 9, 1}; Solution solution; cout << "Largest element: " << solution.largestElement(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 largest value is required.
Maintain the largest value found so far while traversing the array. Whenever a greater value appears, replace the stored candidate with that value.
After every element has been examined, the stored candidate is the largest element.
Algorithm
Initialize
maxElementwithnums[0], giving us a valid array element as the first candidate for the maximum. This also works correctly when all values are negative.Start traversing from index
1, since the first element has already been considered while initializingmaxElement.Compare each current element with
maxElementto check whether a larger value has been found.If the current element is greater, update
maxElementso it always stores the largest value seen so far.Return
maxElementafter the traversal, as every element has been checked against the current maximum.
Dry Run
Maximum Element in Array Optimal Dry Run.png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: int largestElement(const vector<int>& nums) { // The first element provides the initial valid candidate. int maxElement = nums[0]; // Compare every remaining value with the largest found so far. for (int index = 1; index < nums.size(); index++) { if (nums[index] > maxElement) { maxElement = nums[index]; } } return maxElement; }};int main() { vector<int> nums = {5, 2, 9, 1}; Solution solution; cout << "Largest element: " << solution.largestElement(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 maxElement requires auxiliary storage.
Interview follow-up Questions
The initial candidate should be an actual array element. Using 0 could produce an incorrect result when every value in the array is negative.
Be the first to add a comment.