Back to top

Greedy

Overview

In the subsequent sections, we will be providing different patterns of programming questions commonly asked in coding interviews which can be solved using greedy algorithm approach. We don’t want to overwhelm our readers with a plethora of questions. So, we have done the heavy lifting for you by going through almost all the questions on leetcode and categorizing the different patterns of questions commonly asked in the interviews.

Pattern 1: Applications Based

Prob 406: Queue Reconstruction Height

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We need to reconstruct the queue by height.
         * https://leetcode.com/problems/queue-reconstruction-by-height/
         *
         * Approach: We sort the array of people using the height from shortest
         * to tallest. After that we place the elements of the array in a list using the
         * number of people who should be infront of this person who have a height
         * greater than or equal to that particular element.
         *
         * Time Complexity: O(nlgn)
         * Space Complexity: O(n)
         *
         */
        public int[][] reconstructQueue(int[][] people) {
            Arrays.sort(people, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
            List<int[]> res = new ArrayList<>();
            for(int[] p : people){
                res.add(p[1], p);
            }
            int n = people.length;
            return res.toArray(new int[n][2]);
        }

Prob 44: Wildcard matching

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We need to implement a wildcard matching algorithm
         * between a pattern and a string.
         * https://leetcode.com/problems/wildcard-matching/
         *
         * Approach: We will use a dynamic-programming based approach
         * to keep track of the pattern matching algorithm. We use a 2-D matrix
         * to persist the matches between the pattern and the string. If the element
         * in the pattern matches the one in the string then we rely on the
         * match result obtained so far without those specific elements(so dp[i-1][j-1]).
         * Otherwise, we check if the current element in the pattern is "*" in which
         * case we either check for the match results by either removing a character
         * from the string or th pattern.
         *
         * Time Complexity: O(mn)
         * Space Complexity: O(mn)
         *
         */
        public boolean isMatch(String s, String p) {
            int n = s.length();
            int m = p.length();
            boolean[][] dp = new boolean[n+1][m+1];
            dp[0][0] = true;    //s and p are empty
            for(int j = 0; j<m+1; j++){
                 if(j != 0 && p.charAt(j-1) == '*')   //s is empty and p is '*'
                     dp[0][j] = dp[0][j-1];     //imp step
            }
            for(int i = 1; i<n+1; i++)
                for(int j = 1; j<m+1; j++){
                    if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?')
                        dp[i][j] = dp[i-1][j-1];
                    else if(p.charAt(j-1) == '*')
                        dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }
            return dp[n][m];
        }

Pattern 2: Jump Game-Based

Prob 55: Jump Game

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

        /**
         * We need to determine if we are able to reach the last index
         * https://leetcode.com/problems/jump-game/
         *
         * Approach: We keep iterating through the elements and keep track
         * of the index which can be reached from the current index. At the end,
         * if the index is more than the last index then we return true.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(1)
         *
         */
        public boolean canJump(int[] nums) {

            int minReach = 0; int lastIndex = nums.length -1;
            for(int i=0; i <= minReach && minReach < lastIndex; i++)
                minReach = Math.max(minReach, i+nums[i]);
            return minReach >= lastIndex;

        }

Prob 45: Jump Game II

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

       /**
         * We want to find the minimum number of jumps
         * to reach the last index.
         * https://leetcode.com/problems/jump-game-ii/
         *
         * Approach: We keep on iterating through the array to
         * keep track of the number of jumps and the index
         * to which the jump can be made.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(1)
         *
         */
        public int jump(int[] nums) {
            if(nums == null || nums.length == 0) {
                return 0;
            }
            int jumps=0, currreach=0, maxreach=0;
            for(int i=0; i<nums.length; i++){
                if(currreach<i){
                    jumps++;
                    currreach=maxreach;
                }
                maxreach=Math.max(maxreach, i + nums[i]);
            }
            return jumps;
        }

Pattern 3: Stock Buy and Sell

Prob 122: Best time to buy and sell II

NOTE: We recommend you to solve the problem at your end before reading further.

Solution:

        /**
         * We need to find the max profit which can be made by buying
         * and selling stock multiple time.
         * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
         *
         * Approach: We iterate through all the prices in the array and keep
         * on adding the possible profits which can be made in consecutive
         * elements.
         *
         * Time Complexity: O(n)
         * Space Complexity: O(1)
         *
         */
        public int maxProfit(int[] prices) {
            int profit = 0;
            for(int i=0;i<prices.length-1;i++){
                if(prices[i+1] > prices[i]){
                    profit += prices[i+1] - prices[i];
                }
            }
            return profit;
        }