Count occurrences of a number in a sorted array with duplicates
Given a sorted integer array containing duplicates, count occurrences of a given number. If the element is not found in the array, report that as well.
Tag: Medium
Search an element in a circularly sorted array
Given a circularly sorted integer array, search an element in it. Assume there are no duplicates in the array, and the rotation is in the anti-clockwise direction.
Print all triplets that form an arithmetic progression
Given a sorted array of distinct positive integers, print all triplets that forms an arithmetic progression with an integral common difference.
Print all triplets that form a geometric progression
Given a sorted array of distinct positive integers, print all triplets that forms a geometric progression with an integral common ratio.
Remove all extra spaces from a string
Write a program to in-place remove all extra spaces from a string. There maybe leading spaces, trailing spaces, or consecutive spaces between words of the string.
Find maximum sum submatrix present in a matrix
Given an N × N matrix, find the maximum sum submatrix present in it.
Calculate the sum of all elements in a submatrix in constant time
Given an M × N matrix and two coordinates (p, q) and (r, s) representing top-left and bottom-right coordinates of a submatrix of it, calculate the sum of all elements present in the submatrix.
Report all occurrences of an element in a row-wise and column-wise sorted matrix in linear time
Given an M × N matrix, which is row-wise and column-wise sorted (with all strictly increasing elements in any row or column), report all occurrences of a given element in it in linear time.
Find the probability that a person is alive after taking `n` steps on an island
An island is in the form of a square matrix, and a person is standing inside the matrix. The person can move one step in any direction (right, left, top, down) in the matrix. Calculate the probability that the person is alive after walking n steps on the island, provided that he dies if he steps outside the matrix.
Replace all occurrences of 0 that are not surrounded by 1 in a binary matrix
Given an M × N binary matrix, replace all occurrences of 0’s by 1’s, which are not completely surrounded by 1’s from all sides (top, left, bottom, right, top-left, top-right, bottom-left, and bottom-right).
Find all paths from the first cell to the last cell of a matrix
Given an M × N matrix, find all paths from the first cell to the last cell. We can only move down or to the right from the current cell.
Print diagonal elements of a matrix having a positive slope
Given an M × N matrix, print all its diagonal elements having a positive slope… The idea is to start from each cell of the first column of the matrix to print / diagonal for the matrix’s upper-left half.