Max Number of Coins (Coding Problem By Zillow)

 

You are given a 2-d matrix where each cell represents number of coins in that cell. Assuming we start at matrix[0][0], and can only move right or down, find the maximum number of coins you can collect by the bottom right corner.

For example, in this matrix

0 3 1 1
2 0 0 4
1 5 3 1


The most we can collect is 0 + 2 + 1 + 5 + 3 + 1 = 12 coins.

Solution: https://github.com/cbsingh1/DailyCodingProblems/blob/main/src/main/java/MaxCoinCollector_838.java


public class MaxCoinCollector_838 {
    static int findMaxCoins(int coinMatrix[][]) {

        if (coinMatrix == null) return 0;

        int rows = coinMatrix.length;
        int columns = coinMatrix[0].length;
        int[][] tempMatrix = new int[rows] [columns];

        tempMatrix[0] [0] = coinMatrix[0] [0];

        for (int c = 1; c < columns; c++)
            tempMatrix[0] [c] = tempMatrix[0] [c - 1] + coinMatrix[0] [c];

        for (int r = 1; r < rows; r++)
            tempMatrix[r] [0] = tempMatrix[r - 1] [0] + coinMatrix[r] [0];

        for (int r = 1; r < rows; r++)
            for (int c = 1; c < columns; c++)
                tempMatrix[r] [c] = Math.max(tempMatrix[r - 1] [c], tempMatrix[r] [c - 1]) + coinMatrix[r] [c];

        return tempMatrix[rows - 1] [columns - 1];
    }

    //Drive Program
    public static void main(String[] args) {

        int [][] coinMatrix = {{0,3, 1, 1}, {2,0, 0, 4}, {1,5,3,1}};
        System.out.println("Max coin : " + findMaxCoins(coinMatrix));
    }
}
































Comments











Post a Comment



















Popular posts from this blog









Sliding Window Maximum (Maximum of all subarrays of size k) - Java Solution - Leetcode 239




















Image







Solution approach : We will be using sliding window. Deque will be used to store useful element of current subarray. Add first element to deque. Then for adding next element, check if earlier elements are smaller, then remove all elements from deque. Maximum will always be at front of deque. For sliding and removing, check if arr[i] == front of queue, then remove the element. import java.util.Arrays ; import java.util.Deque ; import java.util.LinkedList ; public class MaxOfAllSubarrays {     private static int [] findMaxOfAllSubArrays ( int [] arr , int subArraySize) {         int [] answerArr = new int [arr. length - subArraySize + 1 ] ;         int i = 0 , j = 0 , count = 0 ;         Deque<Integer> deque = new LinkedList<>() ;         while (j < arr. length ) {             while (!deque.isEmpty() && deque.getLast() < arr[j])                 deque.removeLast() ;             deque.add(arr[j]) ;             if (j - i + 1 == subArraySize) {                 answe...








Read more










Count occurrence of anagrams in String




















Image







We would be solving this problem using  Sliding Window approach with 1 Hashmap First we will populate pattern map with occurrence of chars in pattern map. Additionally, a new indicator distinctCharsInMapValueMoreThanZero  will be created. It's initial value would be map.size(). This variable is for numbers of chars in map with value > 0. This will ensure we don't have to compare all values of map to see, if all characters are zero or not. When variable  distinctCharsInMapValueMoreThanZero is zero, it means current substring is anagram of pattern.  When traversing string via Sliding window, we will keep reduce count of character in pattern map. In map, we will not push any char, which are not part of pattern.








Read more





























 Shell Sort Implementation program in Java https://github.com/cbsingh1/DailyCodingProblems/blob/main/src/main/java/com/cbsingh/sorting/ShellSortImpl.java   








Read more