Check if any column has increasing elements in given range for Q queries

Namachila October 13, 2025

0 0 8 minutes read

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 3^rd query elements in 3^rd columns are sorted.
For the 4^th query elements in 3^rd or 4^th columns are sorted.
For the 5^th query elements in first column are sorted.
For the 6^th 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 i^th 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 i^th 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.
Initialize an array (say ans[]) to store the maximum length of increasing subarray finishing at i^th 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 precomputation
void 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 queries
vector<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 code
int 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 approach
import java.util.*;
class GFG{
 
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 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 code
public 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 approach
dp = [[0 for x in range(1005)] for y in range(1005)]
ans = [0]*1005
 
# Function to perform the precomputation
def 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 queries
def 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 res
 
 
N = 5
M = 4
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]]
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 approach
using 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 zambiatek!