## Posts

Showing posts from June, 2021

### Maximum Product Difference: NLogN

Problem can be solved in NLogN with 2 lines: sort and take the extremes. That's it. Problem and code are below, cheers, ACC. Maximum Product Difference Between Two Pairs - LeetCode 1913. Maximum Product Difference Between Two Pairs Easy 33 1 Add to List Share The  product difference  between two pairs  (a, b)  and  (c, d)  is defined as  (a * b) - (c * d) . For example, the product difference between  (5, 6)  and  (2, 7)  is  (5 * 6) - (2 * 7) = 16 . Given an integer array  nums , choose four  distinct  indices  w ,  x ,  y , and  z  such that the  product difference  between pairs  (nums[w], nums[x])  and  (nums[y], nums[z])  is  maximized . Return  the  maximum  such product difference .   Example 1: Input: nums = [5,6,2,7,4] Output: 34 Explanation: We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4). The product difference is (6 * 7) - (2 * 4) = 34. Example 2: Input: nums = [4,2,5,9,7,4,8] Output: 64 Explanation: We can ch

### Count Sub Islands: BFS

Problem can be solved with either a DFS or BFS, decided to go with BFS: 1/ Parse grid2 looking for islands. Use BFS to find them. Store them (O(N)) 2/ Go thru the list of islands from #1, check whether they exist in grid1 (O(N)) Code is below, happy Father's Day!!! ACC Count Sub Islands - LeetCode 1905. Count Sub Islands Medium 160 6 Add to List Share You are given two  m x n  binary matrices  grid1  and  grid2  containing only  0 's (representing water) and  1 's (representing land). An  island  is a group of  1 's connected  4-directionally  (horizontal or vertical). Any cells outside of the grid are considered water cells. An island in  grid2  is considered a  sub-island  if there is an island in  grid1  that contains  all  the cells that make up  this  island in  grid2 . Return the  number  of islands in  grid2   that are considered  sub-islands .   Example 1: Input: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,

### Friday hack on a BST

Not super proud of my solution, but sometimes you need to be pragmatic. Here is the problem:  Depth of BST Given Insertion Order - LeetCode 1902. Depth of BST Given Insertion Order Medium 15 0 Add to List Share You are given a  0-indexed  integer array  order  of length  n , a  permutation  of integers from  1  to  n  representing the  order  of insertion into a  binary search tree . A binary search tree is defined as follows: The left subtree of a node contains only nodes with keys  less than  the node's key. The right subtree of a node contains only nodes with keys  greater than  the node's key. Both the left and right subtrees must also be binary search trees. The binary search tree is constructed as follows: order[0]  will be the  root  of the binary search tree. All subsequent elements are inserted as the  child  of  any  existing node such that the binary search tree properties hold. Return  the  depth  of the binary search tree . A binary tree's  depth  is the number

### Reduction Operations using Priority Queue

This is my 859th solved problem on Leetcode. Took me several attempts before getting a working solution. The problem asks to reduce an array to the same element using pre-defined operations. From the get-go it looked to me like a problem that could be solved using a Priority Queue. Initial attempts failed since I was simulating one operation at a time. When I realized that one can simulate multiple operations at a time, it finally worked. Code is below, cheers, ACC. Reduction Operations to Make the Array Elements Equal - LeetCode 1887. Reduction Operations to Make the Array Elements Equal Medium 101 5 Add to List Share Given an integer array  nums , your goal is to make all elements in  nums  equal. To complete one operation, follow these steps: Find the  largest  value in  nums . Let its index be  i  ( 0-indexed ) and its value be  largest . If there are multiple elements with the largest value, pick the smallest  i . Find the  next largest  value in  nums   strictly smaller  than  la