Essential Array Algorithms: Span, Second Largest, Floor, Ceil, and Bitonic Search
1. Span of Array
Problem Statement:
Find the span of an array (the difference between the maximum and minimum elements).
Example:
Input: [3, 4, 7, 10, 1]
Output: 9 (since 10 - 1 = 9)
Approach:
- Initialize
max = -∞andmin = +∞. - Traverse the array once:
- Update
maxif the current element is greater thanmax. - Update
minif the current element is less thanmin.
- Update
- Return
max - min.
Time Complexity: O(n)
Space Complexity: O(1)
2. Second Largest Element
Problem Statement:
Find the second largest element in an array without sorting it.
Example:
Input: [20, 42, 99, 10, 88, 6]
Output: 88
Approach:
- Initialize two variables:
max1(largest) andmax2(second largest). - Compare the first two elements to set initial values for
max1andmax2. - From the third element onward, iterate:
English with a size of 4.59 KB