1.
Given an integer array of coins[ ] of size N representing different types of currency and an
integer sum, The task is to find the number of ways to make sum by using different
combinations from coins[].
Note: Assume that you have an infinite supply of each type of coin.
Input: sum = 4, coins[] = {1,2,3},
Output: 4
Explanation: there are four solutions: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}
Solution:
public int coinchange(int[] a, int sum, int n, int[][] dp)
{
if (sum == 0)
return dp[n][sum] = 1;
if (n == 0)
return 0;
if (dp[n][sum] != -1)
return dp[n][sum];
if (a[n - 1] <= sum) {
// Either Pick this coin or not
return dp[n][sum]
= coinchange(a, sum - a[n - 1], n, dp)
+ coinchange(a, sum, n - 1, dp);
}
else // We have no option but to leave this coin
return dp[n][sum] = coinchange(a, sum, n - 1, dp);
}
Time Complexity: O(N*sum)
Auxiliary Space: O(N*sum)
2. A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at
a time. Implement a method to count how many possible ways the child can run up the
stairs.
Input : 3
Output : 4
Explanation:
Below are the four ways
1 step + 1 step + 1 step
1 step + 2 step
2 step + 1 step
3 step
Solution:
private int findStepHelper(int n, int[] dp)
{
// Base Case
if (n == 0)
return 1;
else if (n < 0)
return 0;
// If subproblems are already calculated
//then return it
if (dp[n] != -1) {
return dp[n];
}
// store the subproblems in the vector
return dp[n] = findStepHelper(n - 3, dp)
+ findStepHelper(n - 2, dp)
+ findStepHelper(n - 1, dp);
}
// Returns count of ways to reach n-th stair
// using 1 or 2 or 3 steps.
public int findStep(int n)
{
int[] dp = new int[n + 1];
Arrays.fill(dp,-1);
return findStepHelper(n, dp);
}
Time Complexity: O(n). Only one traversal of the array is needed. So Time Complexity is O(n).
Space Complexity: O(n). To store the values in a DP, n extra space is needed. Also, stack space for
recursion is needed which is again O(n)
3. Given an array arr[] of size N, the task is to find the length of the Longest Increasing
Subsequence (LIS) i.e., the longest possible subsequence in which the elements of the
subsequence are sorted in increasing order.
Input: arr[] = {3, 10, 2, 1, 20}
Output: 3
Explanation: The longest increasing subsequence is 3, 10, 20
Solution:
static int f(int idx, int prev_idx, int n, int a[],
int[][] dp)
{
if (idx == n) {
return 0;
}
if (dp[idx][prev_idx + 1] != -1) {
return dp[idx][prev_idx + 1];
}
int notTake = 0 + f(idx + 1, prev_idx, n, a, dp);
int take = Integer.MIN_VALUE;
if (prev_idx == -1 || a[idx] > a[prev_idx]) {
take = 1 + f(idx + 1, idx, n, a, dp);
}
return dp[idx][prev_idx + 1]
= Math.max(take, notTake);
}
// The wrapper function for _lis()
static int lis(int arr[], int n)
{
// The function _lis() stores its result in max
int dp[][] = new int[n + 1][n + 1];
for (int row[] : dp)
Arrays.fill(row, -1);
return f(0, -1, n, arr, dp);
}
Time Complexity : O(n*n)
Auxiliary Space: O(n*n)
4. Given a set of non-negative integers, and a value sum, determine if there is a subset of the
given set with sum equal to given sum.
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
There is a subset (4, 5) with sum 9.
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
There is no subset that add up to 30.
Solution:
static int subsetSum(int a[], int n, int sum)
{
// Storing the value -1 to the matrix
int tab[][] = new int[n + 1][sum + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
tab[i][j] = -1;
}
}
// If the sum is zero it means
// we got our expected sum
if (sum == 0)
return 1;
if (n <= 0)
return 0;
// If the value is not -1 it means it
// already call the function
// with the same value.
// it will save our from the repetition.
if (tab[n - 1][sum] != -1)
return tab[n - 1][sum];
// if the value of a[n-1] is
// greater than the sum.
// we call for the next value
if (a[n - 1] > sum)
return tab[n - 1][sum]
= subsetSum(a, n - 1, sum);
else {
// Here we do two calls because we
// don't know which value is
// full-fill our criteria
// that's why we doing two calls
if (subsetSum(a, n - 1, sum) != 0
|| subsetSum(a, n - 1, sum - a[n - 1])
!= 0) {
return tab[n - 1][sum] = 1;
}
else
return tab[n - 1][sum] = 0;
}
}
TC: O(n*sum)
SC: O(n*sum)
5. Given a n*n matrix where all numbers are distinct, find the maximum length path (starting
from any cell) such that all cells along the path are in increasing order with a difference of 1.
We can move in 4 directions from a given cell (i, j), i.e., we can move to (i+1, j) or (i, j+1) or (i-
1, j) or (i, j-1) with the condition that the adjacent cells have a difference of 1.
Example:
Input: mat[][] = {{1, 2, 9}
{5, 3, 8}
{4, 6, 7}}
Output: 4
The longest path is 6-7-8-9.
Solution:
private static int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // Possible directions: right, down, left,
up
public static int findMaxLength(int[][] matrix) {
int maxLength = 0;
int n = matrix.length;
// Create a memoization map to store the already computed maximum lengths for each cell
Map<String, Integer> memo = new HashMap<>();
// Iterate through each cell and find the maximum length starting from that cell
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int length = dfs(matrix, i, j, memo);
maxLength = Math.max(maxLength, length);
}
return maxLength;
private static int dfs(int[][] matrix, int i, int j, Map<String, Integer> memo) {
int n = matrix.length;
String key = i + "," + j;
// If the maximum length starting from this cell is already computed, return it from memoization
if (memo.containsKey(key))
return memo.get(key);
int maxLength = 1;
// Try all four possible directions from the current cell
for (int[] dir : directions) {
int newRow = i + dir[0];
int newCol = j + dir[1];
// Check if the new cell is within bounds and has a difference of 1 with the current cell
if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n &&
matrix[newRow][newCol] - matrix[i][j] == 1) {
int length = 1 + dfs(matrix, newRow, newCol, memo);
maxLength = Math.max(maxLength, length);
// Store the computed maximum length for this cell in memoization
memo.put(key, maxLength);
return maxLength;
