Leader array questions.

[Question 1] .Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1

Example 1::
Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Explanation: 
- index 0 --> the greatest element to the right of index 0 is index 1 (18).
- index 1 --> the greatest element to the right of index 1 is index 4 (6).
- index 2 --> the greatest element to the right of index 2 is index 4 (6).
- index 3 --> the greatest element to the right of index 3 is index 4 (6).
- index 4 --> the greatest element to the right of index 4 is index 5 (1).
- index 5 --> there are no elements to the right of index 5, so we put -1.
// TC: O(N)
// SC: O(N)
func replaceElements(_ arr: [Int]) -> [Int] {
    let arrayCount = arr.count
    if arrayCount == 0 {return []}
    let lastIndex = arrayCount - 1
    var nums = Array.init(repeating: -1, count: arrayCount)
    var curMax = arr[lastIndex]
    
    nums[lastIndex] = -1// As per question requirement
    
    for i in stride(from: lastIndex - 1, through: 0, by: -1) {
        let temp = curMax
        curMax = max(curMax, arr[i])
        nums[i] = temp
    }
    return nums
}

var leaderArr1 = [10, 22, 12, 3, 0, 6]
let leaderArrayOutput1 = replaceElements(leaderArr1)
print("leaderArrayOutput1 array-->", leaderArrayOutput1) [22, 12, 6, 6, 6, -1]

[Question 2] : Problem Statement: Given an array, print all the elements which are leaders. A Leader is an element that is greater than all of the elements on its right side in the array

Example 1:
Input:
 arr = [4, 7, 1, 0]
Output:
 7 1 0
Explanation:
 Rightmost element is always a leader. 7 and 1 are greater than the elements in their right side.
// TC O(N)
// SC O(N)
func findLeader(arr: [Int]) ->[Int] {
    var leader = arr.last ?? 0
    var leaderArray:[Int] = [leader]//  Last will always leader because no elements are on right
    for obj in stride(from: arr.count-2, to: 0, by: -1) {
        if arr[obj] > leader {// If element is greater than leader append it into new array
            leader = arr[obj]
            leaderArray.append(leader)
        }
    }
    return leaderArray
}

var leaderArr = [10, 22, 12, 3, 0, 6]
let leaderArrayOutput = findLeader(arr: leaderArr)
print("Leader array-->", leaderArrayOutput)//[6, 12, 22]

Leave a Comment

Your email address will not be published. Required fields are marked *