Given an array arr[] consisting of N integers and an array Q[][2] consisting of K queries of type {L, R}, the task for each query is to check if the subarray {arr[L], .. arr[R]} of the array is non-decreasing or not. If found to be true, then print “Yes”. Otherwise, print “No“.
Examples:
Input: arr[] = {1, 7, 3, 4, 9}, K = 2, Q[][] = {{1, 2}, {2, 4}}
Output:
Yes
No
Explanation:
Query 1: The subarray in the range [1, 2] is {1, 7} which is non-decreasing. Therefore, print “Yes”.
Query 2: The subarray in the range [2, 4] is {7, 3, 4, 9} which is not non-decreasing. Therefore, print “No”.Input: arr[] = {3, 5, 7, 1, 8, 2}, K = 3, Q[][] = {{1, 3}, {2, 5}, {4, 6}}
Output:
Yes
No
No
Naive Approach: The simplest approach is to traverse the array over the range of indices [L, R] for each query and check if the subarray is sorted in ascending order or not. If found to be true, then print “Yes”. Otherwise, print “No“.
Time Complexity: O(N * Q)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized by precomputing the count of adjacent elements satisfying arr[i] > arr[i + 1] in the range [1, i] which results in constant time calculation of numbers of such indices in the range [L, R – 1]. Follow the steps below to solve the problem:
- Initialize an array, say pre[], to store the count of indices from the starting index, having adjacent elements in increasing order.
- Iterate over the range [1, N – 1] and assign pre[i] = pre[i – 1] and then increment pre[i] by 1, if arr[i – 1] > arr[i].
- Traverse the array Q[][] and for each query {L, R}, if pre[R – 1] – pre[L – 1] is 0, then print “Yes”. Otherwise, print “No“.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to perform queries to check if// subarrays over a given range of indices// is non-decreasing or notvoid checkSorted(int arr[], int N, vector<vector<int> >& Q){ // Stores count of indices up to i // such that arr[i] > arr[i + 1] int pre[N] = { 0 }; // Traverse the array for (int i = 1; i < N; i++) { // Update pre[i] pre[i] = pre[i - 1] + (arr[i - 1] > arr[i]); } // Traverse the array Q[][] for (int i = 0; i < Q.size(); i++) { int l = Q[i][0]; int r = Q[i][1] - 1; // If pre[r] - pre[l-1] exceeds 0 if (pre[r] - pre[l - 1] == 0) cout << "Yes" << endl; else cout << "No" << endl; }}// Driver Codeint main(){ int arr[] = { 1, 7, 3, 4, 9 }; vector<vector<int> > Q = { { 1, 2 }, { 2, 4 } }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call checkSorted(arr, N, Q); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to perform queries to check if // subarrays over a given range of indices // is non-decreasing or not static void checkSorted(int[] arr, int N, int[][] Q) { // Stores count of indices up to i // such that arr[i] > arr[i + 1] int[] pre = new int[N]; // Traverse the array for (int i = 1; i < N; i++) { // Update pre[i] if((arr[i - 1] > arr[i])) pre[i] = pre[i - 1] + 1; else pre[i] = pre[i - 1]; } // Traverse the array Q[][] for (int i = 0; i < Q.length; i++) { int l = Q[i][0]; int r = Q[i][1] - 1; // If pre[r] - pre[l-1] exceeds 0 if (pre[r] - pre[l - 1] == 0) System.out.println("Yes"); else System.out.println("No"); } } // Driver Code public static void main(String[] args) { int arr[] = { 1, 7, 3, 4, 9 }; int Q[][] = { { 1, 2 }, { 2, 4 } }; int N = arr.length; // Function Call checkSorted(arr, N, Q); }}// This code is contributed by Dharanendra L V. |
Python3
# Python3 program for the above approach# Function to perform queries to check if# subarrays over a given range of indices# is non-decreasing or notdef checkSorted(arr, N, Q): # Stores count of indices up to i # such that arr[i] > arr[i + 1] pre = [0]*(N) # Traverse the array for i in range(1, N): # Update pre[i] pre[i] = pre[i - 1] + (arr[i - 1] > arr[i]) # Traverse the array Q[][] for i in range(len(Q)): l = Q[i][0] r = Q[i][1] - 1 # If pre[r] - pre[l-1] exceeds 0 if (pre[r] - pre[l - 1] == 0): print("Yes") else: print("No")# Driver Codeif __name__ == '__main__': arr =[1, 7, 3, 4, 9] Q = [ [ 1, 2 ],[ 2, 4 ] ] N = len(arr) # Function Call checkSorted(arr, N, Q)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;public class GFG{ // Function to perform queries to check if // subarrays over a given range of indices // is non-decreasing or not static void checkSorted(int[] arr, int N, int[,] Q) { // Stores count of indices up to i // such that arr[i] > arr[i + 1] int[] pre = new int[N]; // Traverse the array for (int i = 1; i < N; i++) { // Update pre[i] if((arr[i - 1] > arr[i])) { pre[i] = pre[i - 1] + 1; } else { pre[i] = pre[i - 1];} } // Traverse the array Q[][] for (int i = 0; i < Q.GetLength(0); i++) { int l = Q[i,0]; int r = Q[i,1] - 1; // If pre[r] - pre[l-1] exceeds 0 if (pre[r] - pre[l - 1] == 0) { Console.WriteLine("Yes");} else {Console.WriteLine("No");} } } // Driver Code static public void Main (){ int[] arr = { 1, 7, 3, 4, 9 }; int[,] Q = { { 1, 2 }, { 2, 4 } }; int N = arr.Length; // Function Call checkSorted(arr, N, Q); }}// This code is contributed by avanitrachhadiya2155 |
Javascript
<script>// Javascript program for the above approach// Function to perform queries to check if// subarrays over a given range of indices// is non-decreasing or notfunction checkSorted(arr, N, Q){ // Stores count of indices up to i // such that arr[i] > arr[i + 1] var pre = Array(N).fill(0); // Traverse the array for(var i = 1; i < N; i++) { // Update pre[i] pre[i] = pre[i - 1] + (arr[i - 1] > arr[i]); } // Traverse the array Q[][] for(var i = 0; i < Q.length; i++) { var l = Q[i][0]; var r = Q[i][1] - 1; // If pre[r] - pre[l-1] exceeds 0 if (pre[r] - pre[l - 1] == 0) document.write("Yes" + "<br>"); else document.write("No" + "<br>"); }}// Driver Codevar arr = [ 1, 7, 3, 4, 9 ];var Q = [ [ 1, 2 ], [ 2, 4 ] ];var N = arr.length;// Function CallcheckSorted(arr, N, Q);// This code is contributed by noob2000</script> |
Yes No
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
