Given a sorted array arr[] of size N and an integer K, the task is to find Kth smallest element present in the array. The given array has been obtained by reversing subarrays {arr[0], arr[R]} and {arr[R + 1], arr[N – 1]} at some random index R. If the key is not present in the array, print -1.
Examples:
Input: arr[] = { 4, 3, 2, 1, 8, 7, 6, 5 }, K = 2
Output: 2
Explanation: Sorted form of the array arr[] is { 1, 2, 3, 4, 5, 6, 7, 8 }. Therefore, the 2nd smallest element in the array arr[] is 2.Input: arr[] = { 10, 8, 6, 5, 2, 1, 13, 12 }, K = 3
Output: 5
Naive Approach: The simplest approach to solve the problem is to sort the given array arr[] in increasing order and print the Kth smallest element in the array.
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Alternative approach of the above solution: We can sort the array without using any sorting technique which will surely reduce the time complexity. We can just find the pivot point P in the array(around which the rotation occurs) using binary search and just reverse the two subarrays [0, P + 1] and [P + 1, N] using std::reverse() function in C++.
Reversing the subarrays: After finding the pivot point P, just find the reverse of the two subarrays as following:
std::reverse(arr, arr + P + 1);
std::reverse(arr + P + 1, arr + N);
And thus we get the sorted array and we can print the Kth smallest element as arr[K-1].
C++
// C++ program for the above approach.#include <bits/stdc++.h>using namespace std;/* Function to get pivot. For array 4, 3, 2, 1, 6, 5 it returns 3 (index of 1) */int findPivot(int arr[], int low, int high){ // base cases if (high < low) return -1; if (high == low) return low; int mid = (low + high) / 2; /*low + (high - low)/2;*/ if (mid < high && arr[mid] < arr[mid + 1]) return mid; if (mid > low && arr[mid] > arr[mid - 1]) return (mid - 1); if (arr[low] <= arr[mid]) return findPivot(arr, low, mid - 1); return findPivot(arr, mid + 1, high);}// Driver Codeint main(){ // Given Input int arr[] = { 10, 8, 6, 5, 2, 1, 13, 12 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 3; // Function Call int P = findPivot(arr, 0, N - 1); // reversing first subarray reverse(arr, arr + P + 1); // reversing second subarray reverse(arr + P + 1, arr + N); // printing output cout << arr[K - 1]; return 0;}// This code is contributed by Pranjay Vats |
Java
// Java program for the above approach.import java.util.*;class GFG{// Function to get pivot. For array 4, 3, 2, 1, 6, 5// it returns 3 (index of 1) static int findPivot(int arr[], int low, int high){ // Base cases if (high < low) return -1; if (high == low) return low; int mid = (low + high) / 2; /*low + (high - low)/2;*/ if (mid < high && arr[mid] < arr[mid + 1]) return mid; if (mid > low && arr[mid] > arr[mid - 1]) return (mid - 1); if (arr[low] <= arr[mid]) return findPivot(arr, low, mid - 1); return findPivot(arr, mid + 1, high);}static void reverse(int str[], int start, int end) { // Temporary variable to store character int temp; while (start <= end) { // Swapping the first and last character temp = str[start]; str[start] = str[end]; str[end] = temp; start++; end--; }}// Driver Codepublic static void main(String[] args){ // Given Input int arr[] = { 10, 8, 6, 5, 2, 1, 13, 12 }; int N = arr.length; int K = 3; // Function Call int P = findPivot(arr, 0, N - 1); // Reversing first subarray reverse(arr, 0, P); // Reversing second subarray reverse(arr, P, N - 1); // Printing output System.out.print(arr[K - 1]);}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program for the above approach.# Function to get pivot. For array 4, 3, 2, 1, 6, 5# it returns 3 (index of 1)def findPivot(arr, low, high): # Base cases if (high < low): return -1 if (high == low): return low mid = int((low + high) / 2) #low + (high - low)/2; if (mid < high and arr[mid] < arr[mid + 1]): return mid if (mid > low and arr[mid] > arr[mid - 1]): return (mid - 1) if (arr[low] <= arr[mid]): return findPivot(arr, low, mid - 1) return findPivot(arr, mid + 1, high) def reverse(Str, start, end): while (start <= end): # Swapping the first and last character temp = Str[start] Str[start] = Str[end] Str[end] = temp start+=1 end-=1# Given Inputarr = [ 10, 8, 6, 5, 2, 1, 13, 12 ]N = len(arr)K = 3# Function CallP = findPivot(arr, 0, N - 1)# Reversing first subarrayreverse(arr, 0, P)# Reversing second subarrayreverse(arr, P, N - 1) # Printing outputprint(arr[K - 1])# This code is contributed by decode2207. |
C#
// C# program for the above approach.using System;class GFG { // Function to get pivot. For array 4, 3, 2, 1, 6, 5 // it returns 3 (index of 1) static int findPivot(int[] arr, int low, int high) { // Base cases if (high < low) return -1; if (high == low) return low; int mid = (low + high) / 2; /*low + (high - low)/2;*/ if (mid < high && arr[mid] < arr[mid + 1]) return mid; if (mid > low && arr[mid] > arr[mid - 1]) return (mid - 1); if (arr[low] <= arr[mid]) return findPivot(arr, low, mid - 1); return findPivot(arr, mid + 1, high); } static void reverse(int[] str, int start, int end) { // Temporary variable to store character int temp; while (start <= end) { // Swapping the first and last character temp = str[start]; str[start] = str[end]; str[end] = temp; start++; end--; } } static void Main() { // Given Input int[] arr = { 10, 8, 6, 5, 2, 1, 13, 12 }; int N = arr.Length; int K = 3; // Function Call int P = findPivot(arr, 0, N - 1); // Reversing first subarray reverse(arr, 0, P); // Reversing second subarray reverse(arr, P, N - 1); // Printing output Console.Write(arr[K - 1]); }}// This code is contributed by divyesh072019. |
Javascript
<script> // Javascript program for the above approach. /* Function to get pivot. For array 4, 3, 2, 1, 6, 5 it returns 3 (index of 1) */ function findPivot(arr, low, high) { // base cases if (high < low) return -1; if (high == low) return low; let mid = parseInt((low + high) / 2, 10); /*low + (high - low)/2;*/ if (mid < high && arr[mid] < arr[mid + 1]) return mid; if (mid > low && arr[mid] > arr[mid - 1]) return (mid - 1); if (arr[low] <= arr[mid]) return findPivot(arr, low, mid - 1); return findPivot(arr, mid + 1, high); } function reverse(i, j, arr) { let y = j - 1; for(let x = i; x < j; x++) { arr[x] = arr[y]; y--; } } // Given Input let arr = [ 10, 8, 6, 5, 2, 1, 13, 12 ]; let N = arr.length; let K = 3; // Function Call let P = findPivot(arr, 0, N - 1); // reversing first subarray reverse(0, P + 1, arr); // reversing second subarray reverse(P + 1, N, arr); // printing output document.write(arr[K - 1]); // This code is contributed by divyeshrabadiya07.</script> |
Output
5
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: The optimal idea is based on the observation that the Rth element is the smallest element because the elements in the range [1, R] are reversed. Now, if the random index is R, it means subarray [1, R] and [R + 1, N] are sorted in decreasing order. Therefore, the task reduceS to finding the value of R which can be obtained using binary search. Finally, print the Kth smallest element.
Follow the steps below to solve the problem:
- Initialize l as 1 and h as N to store the boundary elements index of the search space for the binary search.
- Loop while the value of l+1 < h
- Store the middle element in a variable, mid as (l+h)/2.
- If arr[l] ≥ arr[mid]. If it is true then check on the right side of mid by updating l to mid.
- Otherwise, update r to mid.
- Now after finding R, if K ≤ R, then the answer is arr[R-K+1]. Otherwise, arr[N-(K-R)+1].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the Kth element in a// sorted and rotated array at random pointint findkthElement(vector<int> arr, int n, int K){ // Set the boundaries for binary search int l = 0; int h = n - 1, r; // Apply binary search to find R while (l + 1 < h) { // Initialize the middle element int mid = (l + h) / 2; // Check in the right side of mid if (arr[l] >= arr[mid]) l = mid; // Else check in the left side else h = mid; } // Random point either l or h if (arr[l] < arr[h]) r = l; else r = h; // Return the kth smallest element if (K <= r + 1) return arr[r + 1 - K]; else return arr[n - (K - (r + 1))];}// Driver Codeint main(){ // Given Input vector<int> arr = { 10, 8, 6, 5, 2, 1, 13, 12 }; int n = arr.size(); int K = 3; // Function Call cout << findkthElement(arr, n, K);}// This code is contributed by mohit kumar 29 |
Java
// Java program for the above approachclass GFG{ // Function to find the Kth element in a// sorted and rotated array at random pointpublic static int findkthElement(int arr[], int n, int K){ // Set the boundaries for binary search int l = 0; int h = n - 1, r; // Apply binary search to find R while (l + 1 < h) { // Initialize the middle element int mid = (l + h) / 2; // Check in the right side of mid if (arr[l] >= arr[mid]) l = mid; // Else check in the left side else h = mid; } // Random point either l or h if (arr[l] < arr[h]) r = l; else r = h; // Return the kth smallest element if (K <= r + 1) return arr[r + 1 - K]; else return arr[n - (K - (r + 1))];}// Driver Codepublic static void main(String args[]){ // Given Input int []arr = { 10, 8, 6, 5, 2, 1, 13, 12 }; int n = arr.length; int K = 3; // Function Call System.out.println(findkthElement(arr, n, K));}}// This code is contributed by SoumikMondal |
Python3
# Python program for the above approach# Function to find the Kth element in a # sorted and rotated array at random pointdef findkthElement(arr, n, K): # Set the boundaries for binary search l = 0 h = n-1 # Apply binary search to find R while l+1 < h: # Initialize the middle element mid = (l+h)//2 # Check in the right side of mid if arr[l] >= arr[mid]: l = mid # Else check in the left side else: h = mid # Random point either l or h if arr[l] < arr[h]: r = l else: r = h # Return the kth smallest element if K <= r+1: return arr[r+1-K] else: return arr[n-(K-(r+1))]# Driver Codeif __name__ == "__main__": # Given Input arr = [10, 8, 6, 5, 2, 1, 13, 12] n = len(arr) K = 3 # Function Call print(findkthElement(arr, n, K) ) |
C#
using System.IO;using System;class GFG { // Function to find the Kth element in a // sorted and rotated array at random point public static int findkthElement(int[] arr, int n, int K) { // Set the boundaries for binary search int l = 0; int h = n - 1, r; // Apply binary search to find R while (l + 1 < h) { // Initialize the middle element int mid = (l + h) / 2; // Check in the right side of mid if (arr[l] >= arr[mid]) l = mid; // Else check in the left side else h = mid; } // Random point either l or h if (arr[l] < arr[h]) r = l; else r = h; // Return the kth smallest element if (K <= r + 1) return arr[r + 1 - K]; else return arr[n - (K - (r + 1))]; } static void Main() { // Given Input int[] arr = { 10, 8, 6, 5, 2, 1, 13, 12 }; int n = arr.Length; int K = 3; // Function Call Console.WriteLine(findkthElement(arr, n, K)); }}// This code is contributed by abhinavjain194. |
Javascript
<script> // Function to find the Kth element in a // sorted and rotated array at random point function findkthElement(arr, n, K) { // Set the boundaries for binary search var l = 0; var h = n - 1, r; // Apply binary search to find R while (l + 1 < h) { // Initialize the middle element var mid = parseInt((l + h) / 2); // Check in the right side of mid if (arr[l] >= arr[mid]) l = mid; // Else check in the left side else h = mid; } // Random point either l or h if (arr[l] < arr[h]) r = l; else r = h; // Return the kth smallest element if (K <= r + 1) return arr[r + 1 - K]; else return arr[n - (K - (r + 1))]; } // Given Input var arr = [10, 8, 6, 5, 2, 1, 13, 12]; var n = arr.length; var K = 3; // Function Call document.write(findkthElement(arr, n, K)); </script> |
Output
5
Time Complexity: O(log(N))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
