Given a matrix(mat[][]), which is sorted row and column-wise in increasing order. Two integers are given, L and R, our task is to count number of elements of the matrix within the range [L, R].
Examples:
Input: L = 3, R = 11, matrix =
{{1, 6, 9}
{2, 7, 11}
{3, 8, 12}}
Output: 6
Explanation:
The elements which are in this range [3, 11] are 3, 6, 7, 8, 9, 11.
Input: L = 20, R = 26, matrix =
{{1, 6, 19}
{2, 7, 31}
{3, 8, 42}}
Output: 0
Explanation:
No element is in this range.
Naive Approach: To solve the problem mentioned above the naive method would be to do a row-wise traversal through the matrix.
For each row, we check each element of that row and if it is in the given range, then we increment count. Finally, we return the count.
Time complexity: O(M * N), where M is the number of rows and N is the number of columns.
Efficient Approach: To optimize the above-mentioned approach:
- First we count the elements which are less than L. Lets consider it as count1. We start traversing from the last element of the first column and this includes the following two steps:
- If the current iterating element is less than L, we increment count1 by corresponding row + 1 as elements in that column above current element (including current element) must be less than L. We increment column index.
- If the current iterating element is greater than or equal to L, we decrement row index. We do this until either row or column index becomes invalid.
- Next we count the elements which are less than or equal to R. Let’s consider it as count2. We start traversing from the last element of first column and this includes two steps:
- If the current iterating element is less than or equal to R, we increment count2 by corresponding row + 1 as elements in that column above the current element (including current element) must be less than or equal to R. We increment column index.
- If the current iterating element is greater than R, we decrement row index. We do this until either row or column index becomes invalid.
- Finally, we return the difference of column2 and column1 which will be the required answer.
Below is the implementation of the above approach:
C++
// C++ implementation to count// all elements in a Matrix// which lies in the given range#include <bits/stdc++.h>using namespace std;#define M 3#define N 3// Counting elements in range [L, R]int countElements(int mat[M][N], int L, int R){ // Count elements less than L int count1 = 0; int row = M - 1, col = 0; while (row >= 0 && col < N) { // Check if the current iterating // element is less than L if (mat[row][col] < L) { count1 += (row + 1); col++; } else { row--; } } // counting elements less // than or equal to R int count2 = 0; row = M - 1, col = 0; while (row >= 0 && col < N) { // Check if the current iterating // element is less than R if (mat[row][col] <= R) { count2 += (row + 1); col++; } else { row--; } } // return the final result return count2 - count1;}// Driver codeint main(){ int mat[M][N] = { { 1, 6, 19 }, { 2, 7, 31 }, { 3, 8, 42 } }; int L = 10, R = 26; cout << countElements(mat, L, R); return 0;} |
Java
// Java implementation to count// all elements in a Matrix// which lies in the given rangeimport java.util.*;import java.lang.*;class GFG{ static int N = 3;static int M = 3;// Counting elements in range [L, R]static int countElements(int[][] mat, int L, int R){ // Count elements less than L int count1 = 0; int row = M - 1, col = 0; while (row >= 0 && col < N) { // Check if the current iterating // element is less than L if (mat[row][col] < L) { count1 += (row + 1); col++; } else { row--; } } // counting elements less // than or equal to R int count2 = 0; row = M - 1; col = 0; while (row >= 0 && col < N) { // Check if the current iterating // element is less than R if (mat[row][col] <= R) { count2 += (row + 1); col++; } else { row--; } } // return the final result return count2 - count1;}// Driver codepublic static void main(String[] args){ int[][] mat = { { 1, 6, 19 }, { 2, 7, 31 }, { 3, 8, 42 } }; int L = 10, R = 26; System.out.println(countElements(mat, L, R));}}// This code is contributed by offbeat |
Python3
# Python3 implementation to count # all elements in a matrix which # lies in the given range M = 3N = 3# Counting elements in range [L, R] def countElements(mat, L, R): # Count elements less than L count1 = 0 row = M - 1 col = 0 while row >= 0 and col < N: # Check if the current iterating # element is less than L if mat[row][col] < L: count1 += (row + 1) col += 1 else: row -= 1 # Counting elements less # than or equal to R count2 = 0 row = M - 1 col = 0 while row >= 0 and col < N: # Check if the current iterating # element is less than R if mat[row][col] <= R: count2 += (row + 1) col += 1 else: row -= 1 # Return the final result return count2 - count1 # Driver code mat = [ [ 1, 6, 19 ], [ 2, 7, 31 ], [ 3, 8, 42 ] ] L = 10R = 26print(countElements(mat, L, R)) # This code is contributed by divyamohan123 |
C#
// C# implementation to count// all elements in a Matrix// which lies in the given rangeusing System;class GFG{ static int N = 3;static int M = 3;// Counting elements in range [L, R]static int countElements(int[,] mat, int L, int R){ // Count elements less than L int count1 = 0; int row = M - 1, col = 0; while (row >= 0 && col < N) { // Check if the current iterating // element is less than L if (mat[row, col] < L) { count1 += (row + 1); col++; } else { row--; } } // counting elements less // than or equal to R int count2 = 0; row = M - 1; col = 0; while (row >= 0 && col < N) { // Check if the current iterating // element is less than R if (mat[row, col] <= R) { count2 += (row + 1); col++; } else { row--; } } // return the final result return count2 - count1;}// Driver codepublic static void Main(){ int[,] mat = { { 1, 6, 19 }, { 2, 7, 31 }, { 3, 8, 42 } }; int L = 10, R = 26; Console.Write(countElements(mat, L, R));}}// This code is contributed by Code_Mech |
Javascript
<script>// Javascript implementation to count// all elements in a Matrix// which lies in the given rangeM = 3;N = 3;// Counting elements in range [L, R]function countElements( mat, L, R){ // Count elements less than L var count1 = 0; var row = M - 1, col = 0; while (row >= 0 && col < N) { // Check if the current iterating // element is less than L if (mat[row][col] < L) { count1 += (row + 1); col++; } else { row--; } } // counting elements less // than or equal to R var count2 = 0; row = M - 1, col = 0; while (row >= 0 && col < N) { // Check if the current iterating // element is less than R if (mat[row][col] <= R) { count2 += (row + 1); col++; } else { row--; } } // return the final result return count2 - count1;} var mat = [ [ 1, 6, 19 ], [ 2, 7, 31 ], [ 3, 8, 42 ] ]; var L = 10, R = 26; document.write( countElements(mat, L, R));// This code is contributed by SoumikMondal</script> |
Output:
1
Time Complexity: O(M + N). M is number of Row and N is number of Column.
Auxiliary Space Complexity: 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!