Given a matrix mat[][] of size N * M, and Q queries each of type {L, R} that denotes a range of row [L, R]. The task is to check if there is at least one column that has elements in increasing order in the given range of rows (i.e., is mat[L][j] ? mat[L+1][j] ? . . . ? mat[R][j] for any j).
Note: Here 1 based indexing is used.
Example:
Input: mat[][] = {{1, 2, 3, 5}, {3, 1, 3, 2}, {4, 5, 2, 3}, {5, 5, 3, 2}, {4, 4, 3, 4}}
Q = 6, queries[][] = {{1, 1}, {2, 5}, {3, 5}, {4, 5}, {1, 3}, {1, 5}}
Output:
YES
NO
YES
YES
YES
NO
Explanation: For the first query 1 element is always sorted.
For the second query, there is no column that is sorted.
For the 3rd query elements in 3rd columns are sorted.
For the 4th query elements in 3rd or 4th columns are sorted.
For the 5th query elements in first column are sorted.
For the 6th query there is no such columns which is sorted.Input: mat[][] = { {1, 2, 3, 4}, {2, 3, 4, 5}, {3, 4, 5, 6}, {4, 5, 6, 7 }}
Q = 5, queries[][] = { {1, 2}, {2, 3}, {3, 4}, {5, 6}, {7, 8}}
Output:
YES
YES
YES
NO
NO
Approach: The problem can be solved using precomputation based on the following idea:
For each column, precalculate the maximum length of the maximum increasing subarray from 1st to ith row. Now while answering each query use the precomputed result to check if the elements in that range are increasing or not.
Follow the steps below to solve the problem:
- Initialize a matrix (say dp[][]) to store the result of precomputation.
- In order to precompute, calculate the maximum length of the maximum increasing subarray containing column elements till row i.
- Traverse in each column from j = 1 to M:
- If the element at ith row is at least the same as (i-1)th row increase then dp[i][j] = dp[i-1][j] + 1.
- Otherwise, dp[i][j] = 1.
- Traverse in each column from j = 1 to M:
- Initialize an array (say ans[]) to store the maximum length of increasing subarray finishing at ith row among all the columns.
- Iterate over the queries:
- If ans[r] for any query is at least same as the length of the range then a column exist which satisfies the given conditions.
- Otherwise, there is no such column.
Below is the implementation of the above approach.
C++14
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;int dp[1005][1005];int ans[1005];// Function to perform the precomputationvoid precompute(vector<int> a[], int N, int M){ // For the first row length will always be 1 for (int j = 0; j < M; j++) dp[j][0] = 1; // Loop to fill the dp[][] array for (int i = 0; i < M; i++) { for (int j = 1; j < N; j++) { // If element at the previous row is // smaller or equal to current element if (a[j][i] >= a[j - 1][i]) dp[i][j] = dp[i][j - 1] + 1; else dp[i][j] = 1; } } // Loop to fill the ans[] array for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { ans[i] = max(ans[i], dp[j][i]); } }}// Function to solve the queriesvector<string> query(vector<int> a[], vector<int> arr[], int Q, int N, int M){ precompute(a, N, M); vector<string> res; for (int i = 0; i < Q; i++) { int l = arr[i][0]; int r = arr[i][1]; r--; l--; // If maximum is greater than r-l+1 // then increasing sequence is possible if (ans[r] >= r - l + 1) res.push_back("YES"); else res.push_back("NO"); } return res;}// Driver codeint main(){ int N = 5, M = 4; vector<int> mat[N] = { { 1, 2, 3, 5 }, { 3, 1, 3, 2 }, { 4, 5, 2, 3 }, { 5, 5, 3, 2 }, { 4, 4, 3, 4 } }; int Q = 6; vector<int> queries[Q] = { { 1, 1 }, { 2, 5 }, { 3, 5 }, { 4, 5 }, { 1, 3 }, { 1, 5 } }; // Function call vector<string> sol = query(mat, queries, Q, N, M); for (auto s : sol) cout << s << "\n"; return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG{static int[][] dp = new int[1005][1005];static int[] ans = new int[1005];// Function to perform the precomputationstatic void precompute(int[][] a, int N, int M){ // For the first row length will always be 1 for (int j = 0; j < M; j++) dp[j][0] = 1; // Loop to fill the dp[][] array for (int i = 0; i < M; i++) { for (int j = 1; j < N; j++) { // If element at the previous row is // smaller or equal to current element if (a[j][i] >= a[j - 1][i]) dp[i][j] = dp[i][j - 1] + 1; else dp[i][j] = 1; } } // Loop to fill the ans[] array for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { ans[i] = Math.max(ans[i], dp[j][i]); } }}// Function to solve the queriesstatic ArrayList<String> query(int[][] a, int[][] arr, int Q, int N, int M){ precompute(a, N, M); ArrayList<String> res = new ArrayList<String>(); for (int i = 0; i < Q; i++) { int l = arr[i][0]; int r = arr[i][1]; r--; l--; // If maximum is greater than r-l+1 // then increasing sequence is possible if (ans[r] >= r - l + 1) res.add("YES"); else res.add("NO"); } return res;}// Driver codepublic static void main(String[] args){ int N = 5, M = 4; int[][] mat = { { 1, 2, 3, 5 }, { 3, 1, 3, 2 }, { 4, 5, 2, 3 }, { 5, 5, 3, 2 }, { 4, 4, 3, 4 } }; int Q = 6; int[][] queries = { { 1, 1 }, { 2, 5 }, { 3, 5 }, { 4, 5 }, { 1, 3 }, { 1, 5 } }; // Function call ArrayList<String> sol = query(mat, queries, Q, N, M) ; for (String s : sol) System.out.println(s);}}// This code is contributed by Pushpesh Raj. |
Python3
# Python code to implement the approachdp = [[0 for x in range(1005)] for y in range(1005)]ans = [0]*1005# Function to perform the precomputationdef precompute(a, N, M): # for the first row length will always be 1 for j in range(M): dp[j][0] = 1 # loop to fill the dp[][] array for i in range(M): for j in range(1, N): # If element at the previous row is # smaller or equal to current element if(a[j][i] >= a[j-1][i]): dp[i][j] = dp[i][j-1] + 1 else: dp[i][j] = 1 # loop to fill the ans[] array for i in range(N): for j in range(M): ans[i] = max(ans[i], dp[j][i])# function to solve the queriesdef query(a, arr, Q, N, M): precompute(a, N, M) res = [] for i in range(Q): l = arr[i][0] r = arr[i][1] r -= 1 l -= 1 # If maximum is greater than r-l+1 then # increasing sequence is possible if(ans[r] >= r-l+1): res.append("YES") else: res.append("NO") return resN = 5M = 4mat = [[1, 2, 3, 5], [3, 1, 3, 2], [4, 5, 2, 3], [5, 5, 3, 2], [4, 4, 3, 4]]Q = 6queries = [[1, 1], [2, 5], [3, 5], [4, 5], [1, 3], [1, 5]]sol = query(mat, queries, Q, N, M)for s in range(len(sol)): print(sol[s])# This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class Program { static int[, ] dp = new int[1005, 1005]; static int[] ans = new int[1005]; // Function to perform the precomputation static void precompute(int[, ] a, int N, int M) { // For the first row length will always be 1 for (int j = 0; j < M; j++) dp[j, 0] = 1; // Loop to fill the dp[][] array for (int i = 0; i < M; i++) { for (int j = 1; j < N; j++) { // If element at the previous row is // smaller or equal to current element if (a[j, i] >= a[j - 1, i]) dp[i, j] = dp[i, j - 1] + 1; else dp[i, j] = 1; } } // Loop to fill the ans[] array for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { ans[i] = Math.Max(ans[i], dp[j, i]); } } } // Function to solve the queries static List<string> query(int[, ] a, int[, ] arr, int Q, int N, int M) { precompute(a, N, M); List<string> res = new List<string>(); for (int i = 0; i < Q; i++) { int l = arr[i, 0]; int r = arr[i, 1]; r--; l--; // If maximum is greater than r-l+1 // then increasing sequence is possible if (ans[r] >= r - l + 1) res.Add("YES"); else res.Add("NO"); } return res; } // Driver code public static void Main() { int N = 5, M = 4; int[, ] mat = { { 1, 2, 3, 5 }, { 3, 1, 3, 2 }, { 4, 5, 2, 3 }, { 5, 5, 3, 2 }, { 4, 4, 3, 4 } }; int Q = 6; int[, ] queries = { { 1, 1 }, { 2, 5 }, { 3, 5 }, { 4, 5 }, { 1, 3 }, { 1, 5 } }; // Function call List<string> sol = query(mat, queries, Q, N, M); foreach(string s in sol) Console.WriteLine(s); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// JavaScript code for the above approach let dp = new Array(1005); for (let i = 0; i < dp.length; i++) { dp[i] = new Array(1005).fill(0); } let ans = new Array(1005).fill(0); // Function to perform the precomputation function precompute(a, N, M) { // For the first row length will always be 1 for (let j = 0; j < M; j++) dp[j][0] = 1; // Loop to fill the dp[][] array for (let i = 0; i < M; i++) { for (let j = 1; j < N; j++) { // If element at the previous row is // smaller or equal to current element if (a[j][i] >= a[j - 1][i]) dp[i][j] = dp[i][j - 1] + 1; else dp[i][j] = 1; } } // Loop to fill the ans[] array for (let i = 0; i < N; i++) { for (let j = 0; j < M; j++) { ans[i] = Math.max(ans[i], dp[j][i]); } } return ans; } // Function to solve the queries function query(a, arr, Q, N, M) { ans = precompute(a, N, M); let res = []; for (let i = 0; i < Q; i++) { let l = arr[i][0]; let r = arr[i][1]; r--; l--; // If maximum is greater than r-l+1 // then increasing sequence is possible if (ans[r] >= r - l + 1) res.push("YES"); else res.push("NO"); } return res; } // Driver code let N = 5, M = 4; let mat = [[1, 2, 3, 5], [3, 1, 3, 2], [4, 5, 2, 3], [5, 5, 3, 2], [4, 4, 3, 4]]; let Q = 6; let queries = [[1, 1], [2, 5], [3, 5], [4, 5], [1, 3], [1, 5]]; // Function call let sol = query(mat, queries, Q, N, M); for (let s of sol) console.log(s + " ")// This code is contributed by Potta Lokesh |
Output
YES NO YES YES YES NO
Time Complexity: O(N*M + Q*M)
Auxiliary Space: O(N*M + N)
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!
