Problem

Given a sorted array that has been rotated an unknown number of times, find the Nth largest element in the array.

Examples

Example 1

1
2
3

Input: arr = [15, 18, 2, 3, 6, 12], N = 3
Output: 6
Explanation: The array was originally [2, 3, 6, 12, 15, 18] and rotated 2 times. The 3rd largest element is 6.

Example 2

1
2
3

Input: arr = [6, 12, 15, 18, 2, 3], N = 1
Output: 18
Explanation: The largest element is 18.

Solution

Method 1 – Finding rotation count in naive way and use Rotation Index Formula

Intuition

The smallest element’s index in the rotated array gives the rotation count. The Nth largest element can be found by adjusting the index using this rotation count.

Approach

  1. Find the index of the minimum element (rotation count).
  2. Calculate the position: (rotation count + N - 1) % array size.
  3. Return the element at that position.

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    int findNthLargest(vector<int>& arr, int n) {
        int k = min_element(arr.begin(), arr.end()) - arr.begin();
        int sz = arr.size();
        return arr[(k + n - 1) % sz];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func findNthLargest(arr []int, n int) int {
    k := 0
    for i, v := range arr {
        if v < arr[k] {
            k = i
        }
    }
    sz := len(arr)
    return arr[(k+n-1)%sz]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int findNthLargest(int[] arr, int n) {
        int k = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[k]) k = i;
        }
        int sz = arr.length;
        return arr[(k + n - 1) % sz];
    }
}
1
2
3
4
5
6
7

class Solution {
    fun findNthLargest(arr: IntArray, n: Int): Int {
        val k = arr.indices.minByOrNull { arr[it] } ?: 0
        val sz = arr.size
        return arr[(k + n - 1) % sz]
    }
}
1
2
3
4

def find_nth_largest(arr: list[int], n: int) -> int:
    k = arr.index(min(arr))
    sz = len(arr)
    return arr[(k + n - 1) % sz]
1
2
3
4
5
6
7

impl Solution {
    pub fn find_nth_largest(arr: Vec<i32>, n: i32) -> i32 {
        let k = arr.iter().enumerate().min_by_key(|&(_, &v)| v).unwrap().0;
        let sz = arr.len();
        arr[(k + n as usize - 1) % sz]
    }
}
1
2
3
4
5
6
7

class Solution {
    findNthLargest(arr: number[], n: number): number {
        const k = arr.indexOf(Math.min(...arr));
        const sz = arr.length;
        return arr[(k + n - 1) % sz];
    }
}

Complexity

  • ⏰ Time complexity: O(n), as finding the minimum element requires scanning the array once.
  • 🧺 Space complexity: O(1), since only a few variables are used for computation.

Method 2 – Binary Search for Nth Largest

Intuition

Since the array is a rotated version of a sorted array, we can use binary search to efficiently locate the Nth largest element by first finding the rotation index and then mapping the Nth largest to its correct position. Here is how we can find the rotation count using binary search - Find the rotation count in rotated sorted array.Find the Kth Largest Integer in the Array

Approach

  1. Use binary search to find the index of the smallest element (rotation point).
  2. The original sorted array’s largest element is at index (rotation index + array size - 1) % array size.
  3. The Nth largest element is at index (rotation index + array size - N) % array size.
  4. Return the element at that index.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int findNthLargest(vector<int>& arr, int n) {
        int l = 0, r = arr.size() - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (arr[m] > arr[r]) l = m + 1;
            else r = m;
        }
        int k = l;
        int sz = arr.size();
        return arr[(k + sz - n) % sz];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func findNthLargest(arr []int, n int) int {
    l, r := 0, len(arr)-1
    for l < r {
        m := l + (r-l)/2
        if arr[m] > arr[r] {
            l = m + 1
        } else {
            r = m
        }
    }
    k := l
    sz := len(arr)
    return arr[(k+sz-n)%sz]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int findNthLargest(int[] arr, int n) {
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (arr[m] > arr[r]) l = m + 1;
            else r = m;
        }
        int k = l;
        int sz = arr.length;
        return arr[(k + sz - n) % sz];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun findNthLargest(arr: IntArray, n: Int): Int {
        var l = 0
        var r = arr.size - 1
        while (l < r) {
            val m = l + (r - l) / 2
            if (arr[m] > arr[r]) l = m + 1
            else r = m
        }
        val k = l
        val sz = arr.size
        return arr[(k + sz - n) % sz]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def find_nth_largest(arr: list[int], n: int) -> int:
    l, r = 0, len(arr) - 1
    while l < r:
        m = l + (r - l) // 2
        if arr[m] > arr[r]:
            l = m + 1
        else:
            r = m
    k = l
    sz = len(arr)
    return arr[(k + sz - n) % sz]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn find_nth_largest(arr: Vec<i32>, n: i32) -> i32 {
        let mut l = 0;
        let mut r = arr.len() - 1;
        while l < r {
            let m = l + (r - l) / 2;
            if arr[m] > arr[r] {
                l = m + 1;
            } else {
                r = m;
            }
        }
        let k = l;
        let sz = arr.len();
        arr[(k + sz - n as usize) % sz]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    findNthLargest(arr: number[], n: number): number {
        let l = 0, r = arr.length - 1;
        while (l < r) {
            const m = l + Math.floor((r - l) / 2);
            if (arr[m] > arr[r]) l = m + 1;
            else r = m;
        }
        const k = l;
        const sz = arr.length;
        return arr[(k + sz - n) % sz];
    }
}

Complexity

  • ⏰ Time complexity: O(log n), as binary search is used to find the rotation index.
  • 🧺 Space complexity: O(1), only a few variables are used for computation.