Boris Coding Blog

I wanted problem 600th to be a hard problem, but after few attempts, I switched back to either an easy of medium one. Turned out this one was easy. Here it is:  https://leetcode.com/problems/find-positive-integer-solution-for-a-given-equation/ 1237. Find Positive Integer Solution for a Given Equation Easy 81 327 Add to List Share Given a function   f(x, y)  and a value  z , return all positive integer pairs  x  and  y  where  f(x,y) == z . The function is constantly increasing, i.e.: f(x, y) < f(x + 1, y) f(x, y) < f(x, y + 1) The function interface is defined like this:  interface CustomFunction { public:   // Returns positive integer f(x, y) for any given positive integer x and y.   int f(int x, int y); }; For custom testing purposes you're given an integer  function_id  and a target  z  as input, where  function_id  represent one function from an secret internal list, on the examples you'll know only two functions from the list.   You may retu

Very interesting problem:  https://leetcode.com/problems/boundary-of-binary-tree/ 545. Boundary of Binary Tree Medium 431 758 Add to List Share Given a binary tree, return the values of its boundary in  anti-clockwise  direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate  nodes .  (The values of the nodes may still be duplicates.) Left boundary  is defined as the path from root to the  left-most  node.  Right boundary  is defined as the path from root to the  right-most  node. If the root doesn't have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees. The  left-most  node is defined as a  leaf  node you could reach when you always firstly travel to the left subtree if exists. If not, travel to the right subtree. Repeat until you reach a leaf node. The  right-most  node is

Problem is here:  https://leetcode.com/problems/maximum-average-subarray-i/ 643. Maximum Average Subarray I Easy 616 101 Add to List Share Given an array consisting of  n  integers, find the contiguous subarray of given length  k  that has the maximum average value. And you need to output the maximum average value. Example 1: Input: [1,12,-5,-6,50,3], k = 4 Output: 12.75 Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75 Note: 1 <=  k  <=  n  <= 30,000. Elements of the given array will be in the range [-10,000, 10,000]. Because it gives the length k, you can perform a direct sliding window approach - as you move out of the current window, calculate the new avg and if it is larger than the max, replace it. Code is below, cheers, ACC. public class Solution {     public double FindMaxAverage(int[] nums, int k)     {         double sum = 0;         double avg = 0;         for (int i = 0; i < nums.Length; i++)         {    

Although this is a typical BFS problem, it does require close attention to details. Here it is:  https://leetcode.com/problems/check-if-there-is-a-valid-path-in-a-grid/ 1391. Check if There is a Valid Path in a Grid Medium 44 63 Add to List Share Given a  m  x  n   grid . Each cell of the  grid  represents a street. The street of  grid[i][j]  can be: 1  which means a street connecting the left cell and the right cell. 2  which means a street connecting the upper cell and the lower cell. 3  which means a street connecting the left cell and the lower cell. 4  which means a street connecting the right cell and the lower cell. 5  which means a street connecting the left cell and the upper cell. 6  which means a street connecting the right cell and the upper cell. You will initially start at the street of the upper-left cell  (0,0) . A valid path in the grid is a path which starts from the upper left cell  (0,0)  and ends at the bottom-right cell  (m - 1, n - 1) .  Th

Problem is here:  https://leetcode.com/problems/four-divisors/submissions/ 1390. Four Divisors Medium 18 33 Add to List Share Given an integer array  nums , return the sum of divisors of the integers in that array that have exactly four divisors. If there is no such integer in the array, return  0 . Example 1: Input: nums = [21,4,7] Output: 32 Explanation: 21 has 4 divisors: 1, 3, 7, 21 4 has 3 divisors: 1, 2, 4 7 has 2 divisors: 1, 7 The answer is the sum of divisors of 21 only. Constraints: 1 <= nums.length <= 10^4 1 <= nums[i] <= 10^5 The code to find the Divisors of a number runs in O(n)-time. Problem is that the constraints make the overall execution time for this problem 10^4 * 10^5 = 10^9, which is intractable. Hence, even with some caching for repeated numbers, the solution timed out. Turns out that the key to optimize this problem is to understand that the number of divisors function is a monotonic  function, hence the moment tha

Problem is here:  https://leetcode.com/problems/cinema-seat-allocation/ A cinema has  n  rows of seats, numbered from 1 to  n  and there are ten seats in each row, labelled from 1 to 10 as shown in the figure above. Given the array  reservedSeats  containing the numbers of seats already reserved, for example,  reservedSeats[i]=[3,8]  means the seat located in row  3  and labelled with  8  is already reserved.  Return the maximum number of four-person families you can allocate on the cinema seats.  A four-person family occupies fours seats  in one row , that are  next to each other . Seats across an aisle (such as [3,3] and [3,4]) are not considered to be next to each other, however, It is permissible for the four-person family to be separated by an aisle, but in that case,  exactly two people  have to sit on each side of the aisle. Example 1: Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]] Output: 4 Explanation: The figure above shows the optimal

I've written about the Collatz Conjecture before, right here:  https://dreaktor.com/2019/05/on-collatz-conjecture.html Coincidentally, this LC problem talks about it. Here it is:  https://leetcode.com/problems/sort-integers-by-the-power-value/ 1387. Sort Integers by The Power Value Medium 16 0 Add to List Share The power of an integer  x  is defined as the number of steps needed to transform  x  into  1  using the following steps: if  x  is even then  x = x / 2 if  x  is odd then  x = 3 * x + 1 For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1). Given three integers  lo ,  hi  and  k . The task is to sort all integers in the interval  [lo, hi]  by the power value in  ascending order , if two or more integers have  the same  power value sort them by  ascending order . Return the  k-th  integer in the range  [lo, hi]  sorted by the power value. Noti