DP Problems

  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int totalAfterDiscount(int[] prices)

   /*

       [2, 3, 1, 2, 4, 2]

       Thus, the discount array
                    will contain:

       [1, 1, 0, 2, 2, 0]

       And actual price of items would be:

       [1, 2, 1, 0, 2, 2]

  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()

   boolean
                    check = totalAfterDiscount(new int[] {2, 3, 1, 2, 4, 2}) == 8;

  
                    {

       return false;

}
                    

 
 

  

  
BuyStock
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int oneTransaction(int[] prices)
  
  
   if(prices ==
                    null || prices.length == 0)
  
   {
>        return 0;>    }>    int min = prices[0];>    int max = 0;>    for(int
  i = 1; i prices.length; ++i)>    {
  
       max
                    = Math.max(max, prices[i] - min);
  
       min
                    = Math.min(min, prices[i]);
  
   }
>    return max;>}
  
  
  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int twoTransactions(int[] prices)
  
  
   //  Consider
                    input of prices:
  
   //  Prices: 1, 4, 5, 7,
                    6, 3, 2, 9
  
   //  Left array is a Max(prior,
                    current - min)
  
   //  Left:   0, 3, 4, 6, 6,
                    6, 6, 8
  
   //  Right array is a Max(prior,
                    max - current), Note: moving from right to left
>    //  Right:  8, 7, 7, 7, 7, 7, 7, 0
  >   
  // 
  Value
  is
  computed by picking sum of max from left and right arrays>    if(prices == null || prices.length == 0)>    {
  >        return 0;>    }
  
   int len
                    = prices.length;
  
   int[] left = new
                    int[len];
  
   int[] right = new int[len];
                    
  
   int min = prices[0];
>    for(int i = 1; i len; ++i)>    {>        left[i] =
  Math.max(left[i - 1],
  prices[i] - min);>        min = Math.min(min, prices[i]);>    }>    int max = prices[len - 1];
  >    for(int i = len - 2; i
  = 0; --i)>    {
  
      
                    right[i] = Math.max(right[i + 1], max - prices[i]);
>        max = Math.max(max, prices[i]);
  
  >   
  }
  
  
   int[]
                    sumArray = new int[len];
  
  
                    Arrays.setAll(sumArray, i - left[i] + right[i]);
>    return
  Arrays.stream(sumArray).max().getAsInt();
  >}
  
  
  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int manyTransactions(int[] prices)
  
  
   if(prices ==
                    null || prices.length == 0)
  
   {
>        return 0;>    }>    int profit = 0;>    for(int i = 1; i
  prices.length; ++i)>    {
  
       int
                    diff = prices[i] - prices[i - 1];
  
      
                    if(diff  0)
  
       {
>            profit += diff;>        }>    }
  
   return
                    profit;
  
}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = oneTransaction(new int[] {1, 4, 5, 7, 6, 3, 2, 9}) == 8;
>    if(!check)
  
  
                    {
  
       return false;
>    }>    check = twoTransactions(new int[] {1,
  4, 5, 7, 6, 3, 2, 9}) == 13;>    if(!check)>    {>        return false;>    }
  
   check =
                    manyTransactions(new int[] {1, 4, 5, 7, 6, 3, 2, 9}) == 13;
>    if(!check)
  
  
                    {
  
       return false;
>    }>    return true;
  
}
                    
  
  
  
 










 
 

  

  
DecodeWays
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int decodeWays(String s)
  
  
   //  A
                    message containing letters from A-Z is being encoded to numbers using the following mapping:
  >   
  // 
  'A'
  - 1, 'B' - 2, ..., 'Z' - 26.
  
  
   //  Given an encoded message containing
                    digits, determine the total number of ways to decode it.
>    if(s == null || s.length() == 0)
  
  >   
  {
  
  
      
                    return 0;
  
   }
>    int[] dp = new int[s.length() + 1];>    dp[0] = 1;>    dp[1] = isValid(s.substring(0,
  1)) ? 1 : 0;pre
  data-role="codeBlock"
  data-info="js" class="language-javascript">    for(int i = 2; i = s.length(); ++i)>    {>       
  if(isValid(s.substring(i - 1, i)))>        {
  
                               dp[i] += dp[i - 1];
  
       }
  
       if(isValid(s.substring(i - 2, i)))
>        {>            dp[i] += dp[i - 2];
  >        }
  
   }
                    
  
   return dp[dp.length - 1];
>}>
  

  
                    
  
static private boolean isValid(String s)
                    
  
>    if(s.charAt(0) == '0')
>    {
  
  
                        return false;
  
   }
>    int val = Integer.parseInt(s);>    return val = 1 && val = 26;
  
}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = decodeWays("2122") == 5;
  
  
                    if(!check)
  
   {
>        return false;>    }>    return true;
  
}
                    
  
  
  
 










 
 

  

  
EditDistance
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int editDistance(String s1, String s2)
  
  
 /*
>  Consider two strings:>  s1 = "saturday", s2 = "sunday">  Initial
  state of
  the dp array>          s u n d a y>      0 | 1 2 3 4 5 6>      ----------------->   s  1 | 0 1 2
  3 4
  5>   a  2 | 1 1 2 3 3 4>   t  3 | 2 2 2 3 4 4>   u  4 | 3 2 3 3 4 5>   r  5 | 4 3 3 4 4 5
  >   d  6 | 5 4 4 3 4 5>   a  7 | 6 5 5 4 3 4>   y  8 | 7 6 6 5 4 3>   */
  
     //   
                    Notes: note "=" for comparing i & j
>    int len1 = s1.length(), len2 =
  s2.length();
  
  >    int[][] dp = new int[len1 + 1][len2 + 1];>    for(int i = 1; i = len2; ++i)>    {>       
  dp[0][i] = i;>    }
  
   for(int
                    i = 1; i = len1; ++i)
  
   {
>        dp[i][0] = i;>    }>    for(int i = 1; i = len1; ++i)>    {
  
      
                    for(int j = 1; j = len2; ++j)
  
       {
                    
  
           if(s1.charAt(i - 1) ==
                    s2.charAt(j - 1))
  
           {
>                dp[i][j] = dp[i - 1][j - 1];>            }pre
  data-role="codeBlock"
  data-info="js" class="language-javascript">            else>            {>                dp[i][j] = 1 +
  min3(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]);>            }>        }>    }
  
   return
                    dp[len1][len2];
  
}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   String s1 =
                    "saturday", s2 = "sunday";
>    int x = editDistance(s1, s2);>   
  boolean
  check
  =
  editDistance(s1, s2) == 3;>    if(!check)
  
  
                    {
  
       return false;
>    }>    return true;
  
}
                    
  
  
  
 










 
 

  

  
EggDrop
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int drop(int floors, int eggs)
  
  
//  Time
                    complexity:    O(nk^2), where n = eggs, k = floors
>//  Auxiliary space:    O(nk)>/*
  
DP Array:
  
Initialize dp[eggs][floors + 1]
>0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
  22 23 24 25 25 27 28
  
0 1 0 0 0 0 0 0 0 0 0  
                    0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
>*/
  
   int[][] dp
                    = new int[eggs][floors + 1];
  
   for(int i =
                    1; i = floors; ++i)
  
   {
>        dp[0][i] = i;>    }>    for(int i = 1; i eggs; ++i)>    {
  
      
                    dp[1][i] = 1;
  
   }
>    for(int egg = 1; egg eggs; ++egg)>    {>        for(int floor = 2; floor =
  floors; ++floor)>        {>            int min = Integer.MAX_VALUE;>           
  for(int currentFloor = 1; currentFloor = floor; ++currentFloor)>            {>                int max =
  Math.max(dp[egg - 1][currentFloor - 1],
  dp[egg][floor - currentFloor]);>                min = Math.min(min, 1 + max);>            }
  >            dp[egg][floor] = min;>        }
  
   }
                    
  
   return dp[eggs - 1][floors];
>}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = drop(105, 2) == 14;
  
   if(!check)
                    
  
   {
>        return false;>    }
  
   return
                    true;
  
}
  
  
  
 










 
 

  

  
Elevator
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int elevator(int capacity, int [] weights)
  
  
   int len =
                    weights.length;
  
   int[][] dp = new int[len +
                    1][capacity + 1];
  
   for(int i = 1; i =
                    len; ++i)
  
   {
>        for(int j = 1; j = capacity; ++j)>        {>            if(weights[i - 1]
  j)>            {
  >                dp[i][j] = Math.max(weights[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i -
  1][j]);
  
           }
>            else>            {>                dp[i][j] = dp[i - 1][j];
  >            }>        }
  
   }
                    
  
   return dp[len][capacity];
>}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = elevator(750, new int[] {420, 200, 150, 780, 350}) == 700;
>    if(!check)
  
  
                    {
  
       return false;
>    }>    return true;
  
}
                    
  
  
  
 










 
 

  

  
Fibonacci
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int fibonacci(int n)
  
  
   if(n  0)
                    
  
   {
>        return -1;>    }
  
   if(n
                     2)
  
   {
>        return n;>    }
  
   int a =
                    0, b = 1, c;
  
   for(int i = 2; i = n;
                    ++i)
  
   {
>        c = a + b;>        a = b;>        b = c;
  
  
                    }
  
   return b;
>}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = fibonacci(14) == 377;
  
   if(!check)
                    
  
   {
>        return false;>    }
  
   return
                    true;
  
}
  
  
  
 










 
 

  

  
GenerateIPAddress
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static ListString generate(String address)
  
  
   //   
                    Consider input: "25525511135" which may also contain fewer characters, i.e. "1111"
  >   
  //    We want to place "." in between and
  patternMatch if it constitutes a valid IP address>    //    For example:>    //   
  "2.5.5.25511135">    //    "2.5.52.5511135">    //    "2.5.525.511135"
  >    //    ...
  
  
                    //    "255.255.11.135 //  Valid"
  
  
                    ListString result = new ArrayList();
>    if(address.length() 4 || address.length()
  
  12)>    {>        return result;>    }
  
   int len
                    = address.length();
  
   String candidate =
                    address;
  
   for(int i = 1; i  len - 2;
                    ++i)
  
   {
>        for(int j = i + 1; j len - 1; ++j)>        {
  >            for(int k = j + 1; k
  len; ++k)>            {>                candidate = candidate.substring(0, k) +
  "." +
  candidate.substring(k);
  
              
                    candidate = candidate.substring(0, j) + "." + candidate.substring(j);
>               
  candidate = candidate.substring(0, i) + "." +
  candidate.substring(i);
  
              
                    if(isValid(candidate))
  
               {
  
                   result.add(candidate);
>                }>                candidate = address;
  >            }>        }
  
   }
                    
  
   return result;
>}>
  

  
                    
  
private static boolean isValid(String ip)
                    
  
>    String[] a = ip.split("\\.");
>    for(String s : a)>    {
  
       int
                    val = Integer.parseInt(s);
  
       if(val 
                    0 || val  255 || s.length()  3)
>        {>            return false;>        }
  
      
                    if(s.length()  1 && val == 0)
>        {>            return false;>        }
  
  
      
                    if(s.length()  1 && val != 0 && s.charAt(0) == '0')
>        {>           
  return
  false;>        }
  
   }
                    
  
   return true;
>}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
  
                    ListString result = generate("25525511135");
>    boolean check =
  result.get(0).equals("255.255.11.135") && pre
  data-role="codeBlock" data-info="js"
  class="language-javascript">            result.get(1).equals("255.255.111.35");>    if(!check)>   
  {
  
      
                    return false;
  
   }
>    result = generate("1111");>    check = result.get(0).equals("1.1.1.1");
  
  
   if(!check)
>    {>        return false;>    }
  
   return
                    true;
  
}
  
  
  
 










 
 

  

  
HouseRobber
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int houseRobber(int[] loot)
  
  
   if(loot ==
                    null || loot.length == 0)
  
   {
>        return 0;>    }>    int[] dp = new int[loot.length];>    dp[0] = loot[0];
  >    dp[1] = Math.max(loot[0], loot[1]);>    for(int i = 2; i loot.length; ++i)>    {
  
      
                    dp[i] = Math.max(dp[i - 2] + loot[i], dp[i - 1]);
>    }
  
   return
                    dp[dp.length - 1];
  
}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = houseRobber(new int [] {1, 2, 3, 4, 10, 5, 6, 4}) == 20;
>    if(!check)
  
  
                    {
  
       return false;
>    }>    return true;
  
}
                    
  
  
  
 










 
 

  

  
KnightMoveProbability
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>public class KnightMoveProbability
  
  
   private
                    static int SIZE = 8;
  
   private static int[]
                    X_MOVES = {2, 1, -1, -2, -2, -1,  1,  2};
  
  
                    private static int[] Y_MOVES = {1, 2,  2,  1, -1, -2, -2, -1};
>
  

  
   private
                    static boolean isValid(int x, int y)
  
   {
                    
  
       return x = 0 && x 
                    SIZE && y = 0 && y  SIZE;
>    }
  

  
   static double computeProbability(int xStart,
                    int yStart, int steps)
  
   {
>        double[][][] dp = new double[SIZE][SIZE][steps
  + 1];
  
>        Arrays.fill(dp[0][0], 1);
>
  
>        for(int step = 1; step = steps;
  ++step)pre
  data-role="codeBlock"
  data-info="js" class="language-javascript">        {>            for(int x = 0; x SIZE; ++x)
  >            {>                for(int y = 0; y SIZE; ++y)>                {>                   
  double probability = 0.0;
  >
  
>                    for(int i = 0; i SIZE; ++i)>                    {
  >                        int nextX = x +
  X_MOVES[i];>                        int nextY = y + Y_MOVES[i];
  >                        if(isValid(nextX, nextY))
  
                       {
>                            probability +=
  dp[x][y][step - 1] / 8.0;>                        }>                    }>
  

  >                    dp[x][y][step] = probability;>                }>            }>        }
  
      
                    return dp[xStart][yStart][steps];
  
   }
  
}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = computeProbability(0, 0, 1) == 0.25 &&
>                   
  computeProbability(0,
  0,
  2)
  ==
  0.0625 &&>                    computeProbability(0, 0, 3) ==
  0.015625;
  
   if(!check)
>    {>        return false;>    }
  
   return
                    true;
  
}
  
  
  
 










 
 

  

  
LongestCommon
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static String longestCommonString(String s1, String s2)
  >    //  Strings: "abxcxyze" and "jxyzkl" have
  "xyz" in common.
  
  
   /*
>            x y z>          a 0 0 0>          b 0 0 0
  >          x 1 0 0>          c 0 0 0>          x 1 0 0>          y 0 1 0>          z 0 0 1
  >          e 0 0 0>   */
  
   int len1
                    = s1.length(), len2 = s2.length();
  
   int[][]
                    dp = new int[len1][len1];
  
   boolean
                    matchFound = false;
  
   for(int i = 0; i 
                    len1; ++ i)
  
   {
>        for(int j = 0; j len2; ++j)>        {>            if(s1.charAt(i) ==
  s2.charAt(j))>            {>                dp[i][j] = 1;>                matchFound = true;
  >            }>        }
  
   }
                    
  
   if(!matchFound)
>    {>        return null;>    }
  
   int max
                    = 0;
  
   int startPos = -1;
>    for(int i = 1; i dp.length; ++i)>    {>        for(int j = 0; j
  dp[0].length;
  ++j)>        {>            if(dp[i][j] == 1)>            {
  >                int len = 1;>                for(int k = 1; k dp.length - i; ++k)pre
  data-role="codeBlock"
  data-info="js" class="language-javascript">                {>                    if(dp[i + k][j + k] == 1)
  >                    {>                        len++;>                    }>                    else
  >                    {>                        break;>                    }>                }
  >                if(len max)>                {>                    max = len;
  >                    startPos = i;>                }>            }>        }
  
   }
                    
  
   return s1.substring(startPos, startPos +
                    max);
  
}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = longestCommonString("abxcxyze", "jxyzkl").equals("xyz");
  >   
  if(!check)>    {>        return false;>    }
  
   return
                    true;
  
}
  
  
  
 










 
 

  

  
LongestIncreasing
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int[] longestIncreasingRun(int[] a)
  
  
   //  input: 
                    {3, 4, 5, 2, 3, 4, 5, 7, 1, 2} - from index 3 to index 7
>    //  dp:     {1, 2, 3, 1, 2, 3, 4,
  5,
  1,
  2}
  
  >    int[] dp = new int[a.length];>    dp[0] = 1;
  
  
                    for(int i = 1; i  a.length; ++i)
  
   {
                    
  
       if(a[i]  a[i - 1])
>        {>            dp[i] = dp[i - 1] + 1;
  >        }
  
      
                    else
  
       {
>            dp[i] = 1;>        }
  
   }
                    
  
   int maxVal = dp[0], maxIndex = 1;
  
   for(int i = 1; i  dp.length; ++i)
>    {>        if (dp[i] maxVal)
  >        {>            maxVal = dp[i];>            maxIndex = i;>        }
  
   }
                    
  
   int minIndex = maxIndex - maxVal + 1;
                    
  
   return new int[] {minIndex, maxIndex};
                    
  
}
  
  
  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int longestIncreasingSubsequence(int[] a)
  
  
   //  {10, 22,
                    9, 33, 21, 50, 41, 60, 80} - {10, 22, 33, 50, 60, 80}
>    //  DP Array:>    //  Initial
  State:                      Final State:>    //  {1, 1, 1, 1, 1, 1, 1, 1, 1}         Data:   {10, 22, 9, 33, 21,
  50,
  41, 60, 80}
  
  
                    //                                      DP:     { 1,  2, 1,  3,  2,  4,  4,  5,  6}
pre
  data-role="codeBlock"
  data-info="js" class="language-javascript">    int[] dp = new int[a.length];>    Arrays.fill(dp, 1);>   
  for(int i = 1; i a.length; ++i)
  >    {
  
      
                    for(int j = 0; j  i; ++j)
  
       {
  
           if(a[i]  a[j] && dp[i]
                    = dp[j])
  
           {
>                dp[i] = dp[j] + 1;>            }>        }>    }
  
   return
                    Arrays.stream(dp).max().getAsInt();
  
}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   int[] result
                    = longestIncreasingRun(new int[] {3, 4, 5, 2, 3, 4, 5, 7, 1, 2});
>    boolean check = result[0]
  ==
  3
  && result[1] == 7;>    if(!check)>    {
  
      
                    return false;
  
   }
>    check = longestIncreasingSubsequence(new int[] {10,
  22, 9, 33, 21, 50, 41, 60, 80}) == 6;
  
  
                    if(!check)
  
   {
>        return false;>    }>    return true;
  
}
                    
  
  
  
 










 
 

  

  
MagicPotion
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>public static int minimalSteps(String ingredients)
  
  
   //  
                    consider the following potion which uses 4 distinct ingredients:
>    //      A, B, A, B, C, A,
  B,
  A,
  B,
  C,
  D
  >    //  special instruction, '*', which means "repeat from the beginning", thus:
  
  
   //  A, B, A, B, C, A, B, A, B, C, D =
                    A,B,*,C,*,D
  
   //  write a function that
                    takes as input an un-encoded potion and returns 
>    // the minimum number of characters
  required
  
  pre
  data-role="codeBlock"
  data-info="js" class="language-javascript">    if(ingredients == null || ingredients.length() == 0)>    {
  >        return 0;>    }
  
   int n =
                    ingredients.length();
  
   int[] dp = new
                    int[n];
  
   Arrays.fill(dp,
                    Integer.MAX_VALUE);
  
   dp[0] = 1;
>    for(int i = 1; i n; ++i)>    {>        dp[i] = Math.min(dp[i], dp[i - 1]
  +
  1);>        if(2 * i + 1 n && ingredients.substring(0, i +
  1).equals(ingredients.substring(i + 1, 2 * i + 2)))>        {>            dp[2 * i + 1] = dp[i] + 1;
  >        }
  
   }
                    
  
   return dp[n - 1];
>}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = minimalSteps("ABCDABCE") == 8 && 
  >            minimalSteps("ABCABCE")
  ==
  5 &&>            minimalSteps("AAAAAA") == 4 && 
  >            minimalSteps("AAAABBBB") == 7
  &&
  
          
                    minimalSteps("ABABCABABCD") == 6;
>    if(!check)
  
  
                    {
  
       return false;
>    }>    return true;
  
}
                    
  
  
  
 










 
 

  

  
MinPathSum
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int minPathSum(int[][] grid)
  
  
   /*
>    Given Input:              DP Array:>    {1, 2, 0, 3},           {1, 3, 3, 6},>    {0,
  4, 3, 2},           {1, 5, 6, 8},>    {0, 2, 1, 5},           {1, 3, 4, 9},>    {3, 1, 0, 4}            {4,
  4, 4, 8}>    */>    if(grid == null || grid.length == 0)
  >    {
  
      
                    return 0;
  
   }
>    int rows = grid.length, cols = grid[0].length;>    int[][] dp = new
  int[rows][cols];>    dp[0][0] = grid[0][0];>    for(int i = 1; i cols; ++i)>    {>      
   dp[0][i] = grid[0][i] + dp[0][i -
  1];>    }
  
   for(int
                    i = 1; i  rows; ++i)
  
   {
>        dp[i][0] = grid[i][0] + dp[i - 1][0];>    }>    for(int i = 1; i rows; ++i)
  
  >    {
  
      
                    for(int j = 1; j  cols; ++j)
  
       {
                    
  
           int min = Math.min(dp[i][j - 1],
                    dp[i - 1][j]);
  
           dp[i][j] =
                    grid[i][j] + min;
  
       }
>    }>    return dp[rows - 1][cols - 1];>}
  
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   int[][] data
                    = {
  
           {1, 2, 0, 3},
>            {0, 4, 3, 2},>            {0, 2, 1, 5},>            {3, 1,
  0, 4}>    };>    boolean check = minPathSum(data) == 8;>    if(!check)
  
  
  
                    {
  
       return false;
>    }>    return true;
  
}
                    
  
  
  
 










 
 

  

  
OneEditDistance
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean oneEditDistance(String s1, String s2)
  
  
   //  Given
                    two string s1 and s2, find if s1 can be converted
>    //  to s2 with exactly one edit.
  >   
  // 
  Input:    Result>    //  s1 = "book", s2 = "books":   yes>    //  s1 = "book"
  s2 = "cook":    yes>    //  s1
  = "fact" s2 = "fat"     
  yes
  
   int len1 = s1.length(), len2 =
                    s2.length();
  
   if(Math.abs(len1 - len2) 
                    1)
  
   {
>        return false;>    }
  
   int
                    count = 0;
  
   int s1Pos = 0, s2Pos = 0;
  
   while(s1Pos  len1 && s2Pos 
                    len2)
  
   {
>        if(s1.charAt(s1Pos) == s2.charAt(s2Pos))>        {
  >            s1Pos++;>           
  s2Pos++;>        }
  
      
                    else
  
       {
>            if(count == 1)>            {>                return
  false;>            }>            if(len1 len2)>            {>                s1Pos++;
  >            }>            else if(len2 len1)>            {>                s2Pos++;
  >            }>            else>            {>                s1Pos++;>                s2Pos++;
  >            }>            count++;>        }
  
   }
                    
  
   if(s1Pos  len1 || s2Pos  len2)
                    
  
   {
>        count++;>    }
  
   return
                    count == 1;
  
}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   String s1 =
                    "book", s2 = "books";
  
  
                    String s3 = "book", s4 = "cook";
>    String s5 = "fact", s6 =
  "fat";
  >    boolean check = oneEditDistance(s1, s2) && 
  >            oneEditDistance(s3, s4) &&
  oneEditDistance(s5, s6);
  
   if(!check)
  
   {
>        return false;>    }
  
   return
                    true;
  
}
  
  
  
 










 
 

  

  
OptimalLocation
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>public class OptimalLocation
  
  
   /*
>    Buildings are designated with 1, obstacles with 2,
  empty land with 0, for example:
  
   1 0 2 0 1
                    
  
   0 0 0 0 0
>    0 0 1 0 0>    Position [1, 2] would be an ideal place to build
  house.>    We update the DP array once for each building, >    setting the
  distance from the given building to
  each available position
  
   For example:
  
   First Iteration:    Second Iteration:   Third
                    Iteration:
  
   0 1 0 5 0           0 6 0 6
                    0           0  9 0 9  0
  
   1 2 3 4
                    5           6 6 6 6 6           9  8 7 8  9
>    2 3 0 5 6           8 8 0 8 8           10 9 0
  9
  10
  
  pre
  data-role="codeBlock"
  data-info="js" class="language-javascript">    */>
  

  
   private
                    static int[] X_MOVES = {1, -1, 0,  0};
  
  
                    private static int[] Y_MOVES = {0,  0, 1, -1};
>    private static int MOVES = 4;>
  
<
    /pre>
    
   private
                    static boolean isValid(int x, int y, int[][] grid)
>    {
  
      
                    return x = 0 && x  grid.length && y = 0 && y  grid[0].length &&
                    grid[x][y] == 0;
  
   }
>
  
>    static int
  computeOptimalDistance(int[][] grid)>    {>        int rows = grid.length, cols = grid[0].length;pre
  data-role="codeBlock"
  data-info="js" class="language-javascript">        int[][] dp = new int[rows][cols];>
  
>       
  Listint[] buildings = new ArrayList();
  >
  
>        for(int i = 0; i rows; ++i)
  >        {>            for(int j = 0; j cols; ++j)>            {>               
  if(grid[i][j] == 1)>                {>                    buildings.add(new int[] {i, j});pre
  data-role="codeBlock"
  data-info="js" class="language-javascript">                }>            }>        }
  
                    
  
       for(int[] buildingPos : buildings)
                    
  
       {
>            boolean[][] visited = new boolean[rows][cols];
>           
  QueueDistancePoint queue = new
  LinkedList();
  
          
                    queue.offer(new DistancePoint(buildingPos[0], buildingPos[1], 0));
>
  

  
          
                    while(!queue.isEmpty())
  
           {
>                DistancePoint distancePoint =
  queue.poll();
  
               for(int i = 0; i
                     MOVES; ++i)
  
               {
>                    int xMove = distancePoint.x +
  X_MOVES[i];
  
                   int yMove =
                    distancePoint.y + Y_MOVES[i];
  
>                    if(isValid(xMove, yMove, grid)
  && !visited[xMove][yMove])
>                    {>                        visited[xMove][yMove] =
  true;>                        dp[xMove][yMove] += distancePoint.distance + 1;
  
                       queue.offer(new
                    DistancePoint(xMove, yMove, distancePoint.distance + 1));
>                    }
  >               
  }
  
  >            }>        }
  
                    
  
       int min = Integer.MAX_VALUE;
>        for(int i = 0; i rows; ++i)
>        {
  >            for(int j = 0; j cols;
  ++j)>            {>                if(grid[i][j] == 0)>                {>                    min
  = Math.min(min, dp[i][j]);>                }>            }>        }
  
                    
  
       return min;
>    }
>
  

  
   static
                    class DistancePoint
  
   {
>        int x, y, distance;>
  
>        DistancePoint(int x, int y, int
  distance)>        {>            this.x = x;>            this.y = y;
  >            this.distance = distance;>        }
  
   }
                    
  
}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   int[][] data
                    = {
  
           {1, 0, 2, 0, 1},
>            {0, 0, 0, 0, 0},>            {0, 0, 1, 0, 0}>    };
  >    boolean check =
  computeOptimalDistance(data) == 7;>    if(!check)>    {
  
      
                    return false;
  
   }
>    return true;>}
  
  
  
 










 
 

  

  
PascalTriangle
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>public class PascalTriangle
  
  
     /*
  
 Used to compute number of ways to choose k items
                    from a set of size n
  
 The formula is: n!/(n -
                    k)!k!
  
 However, using factorials quickly
                    exceeds capacity of an integer
  
 Pascal's
                    Triangle looks like this:
  
               1
                    
  
             1   1
>            1   2   1>          1  3    3   1>        1  4   6    4   1
  >      1  5  
  10  10   5   1>   When saved to array:>   1  1  1  1  1  1>   1  1  1  1  1  1>   1  2  1  1  1 
  1>   1  3  3  1  1  1>   1  4  6  4  1  1>   1  5 10 10  5  1>   */
  
   static
                    int[][] triangle;
  
>    public static int[][] buildTriangle(int size)
  
   {
>        triangle = new int[size][size];>        Arrays.stream(triangle).forEach(a -
  Arrays.fill(a, 1));>
  
>        for(int row = 2; row size;
  ++row)>        {>            for(int col = 1; col row; ++col)>            {>               
  triangle[row][col] = triangle[row -
  1][col - 1] + triangle[row - 1][col];
  
  
           }
>        }>        return triangle;>    }
  

  
   static int combinations(int setSize, int items)
                    
  
   {
>        if(setSize = triangle.length || items = triangle[0].length)
  
  
       {
>            return -1;>        }
  
                    
  
       return triangle[setSize][items];
                    
  
   }
>}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
  
                    buildTriangle(10);
  
   boolean check =
                    combinations(3, 2) == 3;
  
   if(!check)
  
   {
>        return false;>    }
  
   check =
                    combinations(4, 2) == 6;
  
   if(!check)
  
   {
>        return false;>    }
  
   check =
                    combinations(5, 2) == 10 && 
>            combinations(5, 2) == 10;>    if(!check)
  
  
  
                    {
  
       return false;
>    }>    return true;
  
}
                    
  
  
  
 










 
 

  

  
RainWater
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int trapWater(int[] heights)
  
  
   //  To
                    compute "ALL" water trapped.
  
   // 
                    heights = 0  1  0  2  1  0  1  3  2  1  2  1
>    //  left    = 0  1  1  2  2  2  2  3  3  3  3 
  3 
  // 
  height
  the left side can support
  
  
   //  right   = 3  3  3  3  3  3  3  3  2 
                    2  2  1  //  height the right side can support
>    //  diff    = 0  0  1  0  1  2  1  0  0  1 
  0 
  0
  =
  6 
  // 
  min(left, right) - height
  
  
    if(heights == null || heights.length 
                    2)
  
   {
>        return 0;>    }
  
   int len
                    = heights.length;
  
   int[] left = new
                    int[len], right = new int[len];
  
   left[0] =
                    heights[0];
  
   for(int i = 1; i  len;
                    ++i)
  
   {
>        left[i] = Math.max(heights[i], left[i - 1]);>    }>   
  right[len - 1] = heights[len - 1];
  >    for(int i = len - 2; i = 1; --i)>    {
  
      
                    right[i] = Math.max(heights[i], right[i + 1]);
>    }
  
   int
                    total = 0;
  
   for(int i = 0; i  len; ++i)
                    
  
   {
>        total += Math.min(left[i], right[i]) - heights[i];>    }
  >    return total;>}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = trapWater(new int[] {0,  1,  0,  2,  1,  0,  1,  3,  2,  1,  2,  1}) == 6;
pre
  data-role="codeBlock"
  data-info="js" class="language-javascript">    if(!check)>    {
  
      
                    return false;
  
   }
>    return true;>}
  
  
  
 










 
 

  

  
RodCutting
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int maxValue(int[] prices)
  
  
   int[] dp =
                    new int[prices.length + 1];
  
   for(int i = 1;
                    i = prices.length; ++i)
  
   {
>        int max = Integer.MIN_VALUE;>        for(int j = 0; j i; ++j)>        {
  >            max = Math.max(max,
  prices[j] + dp[i - j - 1]);>        }>        dp[i] = max;>    }
  
   return
                    dp[dp.length - 1];
  
}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = maxValue(new int[] {2, 4, 8, 9}) == 10;
>    if(!check)
  
  
                    {
  
       return false;
>    }>    return true;
  
}
                    
  
  
  
 










 
 

  

  
RussianDoll
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>You have a number of envelopes with widths and heights given as a pair of integers (w, h).
  
One envelope can fit into another if and only if
                    both the width and height of one envelope is greater
>than the width and height of the other
  envelope.
  
  >What is the maximum number of envelopes can you Russian doll? (put one inside
  other)
  
This is a MaxIncreasingSubSequence
                    problem after the sort
  
Sort by width ascending
                    then by height descending
  
//  Consider
                    following envelopes:
  
       {7, 9},
>        {9, 7},>        {9, 8},>        {9, 10},>        {10, 8},
  >       
  {11, 5},>        {8, 6},>        //  Note that none of the envelopes can be stackedpre
  data-role="codeBlock"
  data-info="js" class="language-javascript">//  After sort>        {7, 9},>        {8, 6},>        {9,
  10},>        {9, 8},>        {9, 7},>        {10, 8},>        {11, 5},>        //  Note
  that (8, 6) can fit in (9, 10) and (9, 7) can fit in (10, 8)
  
  
  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int russianDollCount(int[][] envelopes)
  
  
  
                    Arrays.sort(envelopes, Comparator.comparingInt((int[] a) - a[0])
>        .thenComparing((int[]
  a)
  -
  a[1], Comparator.reverseOrder()));>    int count = 0;>    for(int i = 1; i envelopes.length; ++i)
  >    {>       
  if(envelopes[i][0] envelopes[i
  - 1][0] && envelopes[i][1]
  envelopes[i - 1][1])
  
       {
>            count++;>        }>    }
  
   return
                    count;
  
}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   int[][]
                    envelopes = {
  
           {7, 9},
>            {9, 7},>            {9, 8},>            {9, 10},
  >            {10, 8},
  >            {11, 5},>            {8, 6},>    };
  
   boolean
                    check = russianDollCount(envelopes) == 2;
  
  
                    if(!check)
  
   {
>        return false;>    }>    return true;
  
}
                    
  
  
  
 










 
 

  

  
StairWalk
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static int countWays(int n)
  
  
   if(n  0)
                    return 0;
  
   if(n == 0) return 1;
>    if(n 3) return n;>    int a = 1, b = 1, c = 2, d;>    for(int
  i = 3; i = n; ++i)>    {>        d = a + b + c;>        a = b;
  >        b = c;>        c = d;
  
  
                    }
  
   return c;
>}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = countWays(10) == 274;
  
   if(!check)
                    
  
   {
>        return false;>    }
  
   return
                    true;
  
}
  
  
  
 










 
 

  

  
StringWildMatch
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean wildMatch(String str, String pat)
  
  
/*
>"Goody", "*d*">--------------------->   0 1 2 3              0 1 2 3
  >----------           ----------
  >0| T T F F           0| T T F F>1| F                 1| F T F F>2| F                 2| F T F F>3|
  F                 3| F T F F>4| F                 4| F T T T>5| F                 5| F T F T>*/
  
   int strLen
                    = str.length();
  
   int patLen = pat.length();
                    
  
   boolean[][] dp = new boolean[strLen +
                    1][patLen + 1];
  
   dp[0][0] = true;
>    //  Init top row>    for(int i = 1; i = patLen; ++i)>    {
  >        if(pat.charAt(i - 1) == '*')>        {
  >            dp[0][i] = dp[0][i - 1];>        }
  
   }
                    
  
   for(int i = 1; i = strLen; ++i)
  
   {
>        for(int j = 1; j = patLen; ++j)>        {>            if(pat.charAt(j - 1) ==
  '*')>            {>                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];>            }
  >            else>            {
  >                if(pat.charAt(j - 1) == '?' || str.charAt(i - 1) == pat.charAt(j - 1))
  
               {
>                    dp[i][j] = dp[i - 1][j - 1];>                }
  >            }>        }
  
   }
                    
  
   return dp[strLen][patLen];
>}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   boolean
                    check = wildMatch("Goody", "*d*");
>    if(!check)
  
  
                    {
  
       return false;
>    }>    check = wildMatch("Good
  Morning", "*ing");>    if(!check)>    {>        return false;>    }
  
   check =
                    wildMatch("Good Morning", "Goo*ing");
>    if(!check)
  
  
                    {
  
       return false;
>    }>    check = !wildMatch("Good
  Morning", "Good *x");>    if(!check)>    {>        return false;>    }
  
   return
                    true;
  
}
  
  
  
 










 
 

  

  
UniquePaths
  
  

  
Tests
  
 
 

  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence> /*
  
Consider following
                    maze:    First row and First column of dp    sum above and to the left if maze[i][j] == 1
pre
  data-role="codeBlock"
  data-info="js" class="language-javascript">    {1, 1, 0, 1},           {1, 1, 0, 1},                       {1, 1, 0, 1},
  
  
   {0, 1, 1, 0},           {0, 0, 0,
                    0},                       {0, 1, 1, 0},
  
  
                    {0, 1, 1, 1},           {0, 0, 0, 0},                       {0, 1, 2, 2},
pre
  data-role="codeBlock"
  data-info="js"
  class="language-javascript">    {0, 0, 1, 1},           {0, 0, 0, 0},                       {0, 0, 2, 4},>    {0,
  0, 1, 1}            {0, 0, 0,
  0},                       {0, 0, 2, 6}
  
*/
                    
  
static int uniquePaths(int [][] maze)
  
>    if(maze == null || maze.length == 0)>    {
  
      
                    return 0;
  
   }
>    int rows = maze.length, cols = maze[0].length;>    int[][] dp = new
  int[rows][cols];>    for(int i = 0; i cols; ++i)>    {>        dp[0][i] = maze[0][i];>    }
  
  
   for(int
                    i = 0; i  rows; ++i)
  
   {
>        dp[i][0] = maze[i][0];>    }>    for(int i = 1; i rows; ++i)
  >    {
  
      
                    for(int j = 1; j  cols; ++j)
  
       {
                    
  
           if(maze[i][j] == 1)
>            {>                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  >            }
  >        }>    }
  
   return
                    dp[rows - 1][cols - 1];
  
}
  
  
  
  

  

  

    
  data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence"
  data-theme=Confluence>static boolean testsPass()
  
  
   int [][]
                    maze = {
  
           {1, 1, 0, 1},
>            {0, 1, 1, 0},>            {0, 1, 1, 1},>            {0, 0,
  1, 1},>            {0, 0, 1, 1}>    };>    boolean check = uniquePaths(maze) == 6;>   
  if(!check)
  
  
  
                    {
  
       return false;
>    }>    return true;
  
}