LATIN SQUARE” and its implementation
Posted on March 27, 2014
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Problem
Understand Latin Square and its implementation
Understanding the latin square
“A Latin square is an n × n array filled with n different Latin letters, each occurring exactly once in each row and exactly once in each column” – Wikipedia. You can find the detail explanation of the properties of this Square here on Wikipedia
In this article we will build a square to match the definition.
[Read More]Unique Paths in 2D grid
Posted on March 19, 2014
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Problem :
There is an m x n grid. One can only move either down or right at any point in time. One is trying to reach the bottom-right corner of the grid.
How many possible unique paths are there?
(project euler problem 15)
The similar question has been asked in Cracking the coding interview: Here we have to count the unique paths, but there we have to find the unique paths.
[Read More]Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0
Posted on February 6, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem Provide an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0
Example **Input : **
1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 Output :
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 Solution Method 1 - Using the extra space and O(n^2) solution
[Read More]Find row with maximum number of 1s in sorted matrix
Posted on January 17, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Problem: You are given a MxN matrix with each row sorted. Matrix is having only 0′s and 1′s. You have to find row wotth maximum number of 1′s.
eg. matrix given:
000111
001111
011111
000011
111111 // row with max number of 1′s
Method 1: Brute force approach
Traverse the matrix row wise and count number of 1′s. If the number of 1′s is greater than max count than store index of row.
[Read More]Find an element in matrix in which rows and columns are sorted
Posted on December 18, 2011
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Problem
Given a matrix in which each row and each column is sorted, write a method to find an element in it.
Example
1 4 7 13 2 5 9 15 3 6 10 16 Solution
Here we can have 2 cases -
Case when array is sorted such that last element of nth row is less than first element of n+1 th row Generic case - simply put rows and columns CASE 1 - If last element of each row is less than first element of next row
[Read More]Spiral printing of a two dimensional array
Posted on September 19, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Given a 2D array, print it in spiral form.
Examples
See the following examples.
Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Output: 1 2 3 4 5 6 12 18 17 16 15 14 13 7 8 9 10 11 Code is :
[Read More]