CodeWithClarity

 You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1]. We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array. Return the largest number of chunks we can make to sort the array.   Example 1: Input: arr = [4,3,2,1,0] Output: 1 Explanation: Splitting into two or more chunks will not return the required result. For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted. Example 2: Input: arr = [1,0,2,3,4] Output: 4 Explanation: We can split into two chunks, such as [1, 0], [2, 3, 4]. However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible. Approach 1 : Using Left Max and Right Min Arrays Idea: Instead of tracking only the maximum, we can also maintain the right minimum values. leftMax[i] : Stores the maximum value from index 0 to i . righ...

 You are given an integer array arr. We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array. Return the largest number of chunks we can make to sort the array.   Example 1: Input: arr = [5,4,3,2,1] Output: 1 Explanation: Splitting into two or more chunks will not return the required result. For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted. Example 2: Input: arr = [2,1,3,4,4] Output: 4 Explanation: We can split into two chunks, such as [2, 1], [3, 4, 4]. However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.   class Solution {     public int maxChunksToSorted ( int [] arr ) {                   int n = arr . length ;         int [] leftmax = new int [n]; // Array to store the maximum values from left to curre...

 Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.   Example 1: Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true Example 2: Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 Output: false Approach Used (Search from Top-Right Corner) Start from the top-right corner of the matrix (row = 0, col = last index) . Compare the element with the target: If it matches, return true . If the target is smaller, move left (decrease col ). If the target is larger, move down (increase row ). Continue this process until either: The element is found ( return true ). The indices go out of bounds ( return false ). Time Com...

  Minimum Swaps to Group All 1's Together II A swap is defined as taking two distinct positions in an array and swapping the values in them. A circular array is defined as an array where we consider the first element and the last element to be adjacent. Given a binary circular array nums, return the minimum number of swaps required to group all 1's present in the array together at any location.   Example 1: Input: nums = [0,1,0,1,1,0,0] Output: 1 Explanation: Here are a few of the ways to group all the 1's together: [0,0,1,1,1,0,0] using 1 swap. [0,1,1,1,0,0,0] using 1 swap. [1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array). There is no way to group all 1's together with 0 swaps. Thus, the minimum number of swaps required is 1. Example 2: Input: nums = [0,1,1,1,0,0,1,1,0] Output: 2 Explanation: Here are a few of the ways to group all the 1's together: [1,1,1,0,0,0,0,1,1] using 2 swaps (using the circular property of the array). [1,1,1,1,1,0,0,...

 Given an array of n positive integers and a number k. Find the minimum number of swaps required to bring all the numbers less than or equal to k together. Input: arr[] = {2, 1, 5, 6, 3}, k = 3 Output: 1 Explanation: To bring elements 2, 1, 3 together, swap element ‘5’ with ‘3’ such that final array will be arr[] = {2, 1, 3, 6, 5} Input: arr[] = {2, 7, 9, 5, 8, 7, 4}, k = 5 Output: 2 📝 Explanation Find the window size → Count numbers ≤ k . Calculate "bad" elements (elements > k ) in the first window. Use Sliding Window : Move the window right (remove old, add new). Track the minimum "bad" count (which gives the min swaps). Return minSwaps as the answer.  Takeaways ✅ We only check a window once → O(n) efficiency ✅ The bad count helps track unnecessary swaps ✅ Sliding one step at a time avoids nested loops (faster) Step-by-Step Execution Step 1: Calculate count (Window Size) The window size is the count of elements ≤ k . Eleme...

 Given a NxN 2-D matrix, the task to find the sum of all the submatrices. Input 1: arr[] = {{1, 1}, {1, 1}}; Output 1: 16 Explanation 1: Number of sub-matrices with 1 elements = 4 Number of sub-matrices with 2 elements = 4 Number of sub-matrices with 3 elements = 0 Number of sub-matrices with 4 elements = 1 Since all the entries are 1, the sum becomes sum = 1 * 4 + 2 * 4 + 3 * 0 + 4 * 1 = 16 Input 2: arr[] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}} Output 2: 500 Simple Solution: A naive solution is to generate all the possible submatrices and sum up all of them.  The time complexity of this approach will be O(n6). Efficient Solution : For each element of the matrix, let us try to find the number of sub-matrices, the element will lie in.  This can be done in O(1) time. Let us suppose the index of an element be (X, Y) in 0 based indexing, then the number of submatrices (Sx, y) for this element will be given by the formula Sx, y = (X + 1) * (Y + 1) * (N – X) * (N – Y). This formula...

 In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data. You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix. The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were. If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix. Example 1: Input: mat = [[1,2],[3,4]], r = 1, c = 4 Output: [[1,2,3,4]] Example 2: Input: mat = [[1,2],[3,4]], r = 2, c = 4 Output: [[1,2],[3,4]] Code : class Solution {     public int [][] matrixReshape ( int [][] mat , int r , int c ) {                 // Get the number of rows and columns in the original matrix         int row = mat . leng...

Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid. Example 1: Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8 Explanation: There are 8 negatives number in the matrix. Example 2: Input: grid = [[3,2],[1,0]] Output: 0 Brute Force: class Solution {     public int countNegatives ( int [][] grid ) {       int row = grid . length ;       int col =grid[ 0 ]. length ;       int negativeCount = 0 ;       for ( int i = 0 ;i<row;i++)      {         for ( int j = 0 ;j<col;j++)         {             if (grid[i][j]< 0 )             {                 negativeCount++;             }         }  ...

 Given a 2D integer array matrix, return the transpose of matrix. The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix's row and column indices. Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[1,4,7],[2,5,8],[3,6,9]] Example 2: Input: matrix = [[1,2,3],[4,5,6]] Output: [[1,4],[2,5],[3,6]] Code 1: class Solution {     public int [][] transpose ( int [][] matrix ) {                   int rows = matrix . length ; // Number of rows         int cols = matrix[ 0 ]. length ; // Number of columns                 int [][] transposed = new int [cols][rows]; // Create a new matrix with swapped dimensions         // Fill the transposed matrix         for ( int i = 0 ; i < rows; i++) {             for ( int j = 0 ; j < cols; j++) {  ...

 A position (i, j) is called special if mat[i][j] == 1 and all other elements in row i and column j are 0 (rows and columns are 0-indexed). Example 1: Input: mat = [[1,0,0],[0,0,1],[1,0,0]] Output: 1 Explanation: (1, 2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0. Example 2: Input: mat = [[1,0,0],[0,1,0],[0,0,1]] Output: 3 Explanation: (0, 0), (1, 1) and (2, 2) are special positions. class Solution {     public int numSpecial ( int [][] mat ) {         int row = mat . length ; // Number of rows in the matrix         int col = mat[ 0 ]. length ; // Number of columns in the matrix         // Arrays to store the count of 1s in each row and column         int [] row_count = new int [row]; // Stores count of 1s in each row         int [] col_count = new int [col]; // Stores count of 1s in each column     ...