⏰ 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

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

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int findNthLargest(vector<int>& arr, int n) {\n        int l = 0, r = arr.size() - 1;\n        while (l < r) {\n            int m = l + (r - l) / 2;\n            if (arr[m] > arr[r]) l = m + 1;\n            else r = m;\n        }\n        int k = l;\n        int sz = arr.size();\n        return arr[(k + sz - n) % sz];\n    }\n};","lang":"cpp"},{"language":"Go","code":"func findNthLargest(arr []int, n int) int {\n    l, r := 0, len(arr)-1\n    for l < r {\n        m := l + (r-l)/2\n        if arr[m] > arr[r] {\n            l = m + 1\n        } else {\n            r = m\n        }\n    }\n    k := l\n    sz := len(arr)\n    return arr[(k+sz-n)%sz]\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int findNthLargest(int[] arr, int n) {\n        int l = 0, r = arr.length - 1;\n        while (l < r) {\n            int m = l + (r - l) / 2;\n            if (arr[m] > arr[r]) l = m + 1;\n            else r = m;\n        }\n        int k = l;\n        int sz = arr.length;\n        return arr[(k + sz - n) % sz];\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun findNthLargest(arr: IntArray, n: Int): Int {\n        var l = 0\n        var r = arr.size - 1\n        while (l < r) {\n            val m = l + (r - l) / 2\n            if (arr[m] > arr[r]) l = m + 1\n            else r = m\n        }\n        val k = l\n        val sz = arr.size\n        return arr[(k + sz - n) % sz]\n    }\n}","lang":"kotlin"},{"language":"Python","code":"def find_nth_largest(arr: list[int], n: int) -> int:\n    l, r = 0, len(arr) - 1\n    while l < r:\n        m = l + (r - l) // 2\n        if arr[m] > arr[r]:\n            l = m + 1\n        else:\n            r = m\n    k = l\n    sz = len(arr)\n    return arr[(k + sz - n) % sz]","lang":"python"},{"language":"Rust","code":"impl Solution {\n    pub fn find_nth_largest(arr: Vec<i32>, n: i32) -> i32 {\n        let mut l = 0;\n        let mut r = arr.len() - 1;\n        while l < r {\n            let m = l + (r - l) / 2;\n            if arr[m] > arr[r] {\n                l = m + 1;\n            } else {\n                r = m;\n            }\n        }\n        let k = l;\n        let sz = arr.len();\n        arr[(k + sz - n as usize) % sz]\n    }\n}","lang":"rust"},{"language":"TypeScript","code":"class Solution {\n    findNthLargest(arr: number[], n: number): number {\n        let l = 0, r = arr.length - 1;\n        while (l < r) {\n            const m = l + Math.floor((r - l) / 2);\n            if (arr[m] > arr[r]) l = m + 1;\n            else r = m;\n        }\n        const k = l;\n        const sz = arr.length;\n        return arr[(k + sz - n) % sz];\n    }\n}","lang":"typescript"}]

Complexity

⏰ Time complexity: O(log n), as binary search is used to find the rotation

Related Tags