Find Second Largest Element
/*
* Find Second Largest is a real technical interview question.
* Chances are you will be asked to find the second largest value
* inside of an array of numbers. You must also be able to filter
* out duplicate values. It's important to know how to do this with
* clean code that is also easy to explain.
*
* Resources:
* https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
*/
const secondLargestElement = (array) => {
const largestElement = Math.max(...array)
let element = -Number.MAX_VALUE
for (let i = 0; i < array.length; i++) {
if (element < array[i] && array[i] !== largestElement) {
element = array[i]
}
}
return element
}
export { secondLargestElement }
이 알고리즘에 대해
Problem statement
Given an unsorted array, write a function to find the second largest element in the array.
Approach
- Find the largest element in the array by traversing through the array using a loop and store the value in a variable (for ex: a )
- Assign a variable to store the negative infinite value, which stores the least value (for ex: b )
- Run a loop from zero to the size of the array.
- Now check whether the current element is greater than variable "b" and also not equal to variable "a", which is the largest number in the array.
- if the above condition is true, then the variable b stores the current element.
Time Complexity
- Best case:
O(n) - Average case:
O(n) - Worst case:
O(n)
Space Complexity
Worst case: O(1)
Example
arr = [2, 5, 3, 9, 12, 34, 25]
Indexes: 0 1 2 3 4 5 6
a = max(arr)
(a = 34)
b = float("-inf")
Traverse elements from i = 0 to i = 6
i = 0
Check if b < arr[i] (arr[0]) and arr[0] != a
True : b = arr[0] (b = 2)
i = 1
Check if b < arr[i] (arr[1]) and arr[1] != a
True : b = arr[0] (b = 5)
i = 2
Check if b < arr[i] (arr[2]) and arr[2] != a
False : As b = 5 is greater than the current element arr[2] = 3
continues with the loop
i = 3
Check if b < arr[i] (arr[3]) and arr[3] != a
True : b = arr[3] (b = 9)
i = 4
Check if b < arr[i] (arr[4]) and arr[4] != a
True : b = arr[4] (b = 12)
i = 5
Check if b < arr[i] (arr[5]) and arr[5] != a
False: As current element is equal to the variable "a" which stores the highest value in the array
continues with the loop
i = 6
Check if b < arr[i] (arr[6]) and arr[6] != a
True : b = arr[6] (b = 25)
Now we get the value 25 in the variable "b", which is the second highest value in the array.
