Another Casual Coder

Many years ago I used the Sieve of Eratosthenes to solve a LC problem. Here is another one. The Sieve allows us to calculate all primes between 1..N in O(N)-time, and O(N)-space. Calculate all non-primes in the very first beginning, then just proceed to execute the calculation asked. Code is down below, Happy New Year, ACC. (1) Closest Prime Numbers in Range - LeetCode 2523. Closest Prime Numbers in Range Medium 41 8 Add to List Share Given two positive integers  left  and  right , find the two integers  num1  and  num2  such that: left <= nums1 < nums2 <= right  . nums1  and  nums2  are both  prime  numbers. nums2 - nums1  is the  minimum  amongst all other pairs satisfying the above conditions. Return  the positive integer array   ans = [nums1, nums2] .  If there are multiple pairs satisfying these conditions, return the one with the minimum   nums1   value or   [-1, -1]   if such numbers do not exist. A number greater than  1  is called  prime  if it is only divisible by  1

This problem is a classic DP problem, and the hints confirm it. Couldn't solve it using DP, and the brute-force DFS approach was leading to TLE. So... decided to try to work around it.  The heuristic used was simple: if we try way too many interactions (say 10x100x100), then we'll assume that there is no solution. It means that we have tried 10 times more cells that exists on the board. It worked. Sometimes achieving the goals requires creative and shameless approaches. Code is down below, cheers, ACC. Check if There is a Path With Equal Number of 0's And 1's - LeetCode 2510. Check if There is a Path With Equal Number of 0's And 1's Medium 11 1 Add to List Share You are given a  0-indexed   m x n   binary  matrix  grid . You can move from a cell  (row, col)  to any of the cells  (row + 1, col)  or  (row, col + 1) . Return  true  if there is a path from  (0, 0)  to  (m - 1, n - 1)  that visits an  equal  number of  0 's and  1 's . Otherwise return  false

This is my 207th Project Euler problem solved (after problem 100th, it gets really intense). This one, problem 816, seemed on the surface "doable", but required some "guess". The standard brute-force solution would lead to an N^2 algorithm, and since N=2x10^6, became intractable. I then decided to use "some sorting criteria". That gave me an opportunity to, using some heuristics (which I cannot disclose here since Project Euler admins would then lock my account), makes it a more tractable problem. In this case I won't even post the screenshot of the modified code since it will give away pretty easily the heuristic used. But, in case you want to try it, it is a fun problem. Cheers, ACC.

Interesting problem: build a memory allocator class. Given the small n (1000), approach was the following: 1/ Keep track of the memory as an array of integers 2/ Keep track of the total size allocated for mID (HashTable) 3/ Keep track of which mIDs have been freed up (HashTable) 4/ To allocate, scan the memory array looking for a consecutive free block. Allocate it if found. There is some math needed here to ensure the proper allocation, simple math with the indexes. There is some perf optimization that can be done with a "jump" table, but again n=1000, there is no need 5/ To free, just operate with the HashTables in #2 and #3 above Code is down below, cheers, ACC. Design Memory Allocator - LeetCode 2502. Design Memory Allocator Medium 128 58 Add to List Share You are given an integer  n  representing the size of a  0-indexed  memory array. All memory units are initially free. You have a memory allocator with the following functionalities: Allocate  a block of  size  consecut

This question just requires a sorting (nlogn), two-pointers (n) and conversion to long. Code is down below, cheers, ACC. Divide Players Into Teams of Equal Skill - LeetCode 2491. Divide Players Into Teams of Equal Skill Medium 117 1 Add to List Share You are given a positive integer array  skill  of  even  length  n  where  skill[i]  denotes the skill of the  i th  player. Divide the players into  n / 2  teams of size  2  such that the total skill of each team is  equal . The  chemistry  of a team is equal to the  product  of the skills of the players on that team. Return  the sum of the  chemistry  of all the teams, or return  -1  if there is no way to divide the players into teams such that the total skill of each team is equal.   Example 1: Input: skill = [3,2,5,1,3,4] Output: 22 Explanation: Divide the players into the following teams: (1, 5), (2, 4), (3, 3), where each team has a total skill of 6. The sum of the chemistry of all the teams is: 1 * 5 + 2 * 4 + 3 * 3 = 5 + 8 + 9

Using four HashTables to solve this problem, two for rows, two for columns. Two passes in the matrix, for a time complexity of O(n*m). Code is down below, cheers, ACC. Difference Between Ones and Zeros in Row and Column - LeetCode 2482. Difference Between Ones and Zeros in Row and Column Medium 131 7 Add to List Share You are given a  0-indexed   m x n  binary matrix  grid . A  0-indexed   m x n  difference matrix  diff  is created with the following procedure: Let the number of ones in the  i th  row be  onesRow i . Let the number of ones in the  j th  column be  onesCol j . Let the number of zeros in the  i th  row be  zerosRow i . Let the number of zeros in the  j th  column be  zerosCol j . diff[i][j] = onesRow i  + onesCol j  - zerosRow i  - zerosCol j Return  the difference matrix  diff .   Example 1: Input: grid = [[0,1,1],[1,0,1],[0,0,1]] Output: [[0,0,4],[0,0,4],[-2,-2,2]] Explanation: - diff[0][0] = onesRow 0 + onesCol 0 - zerosRow 0 - zerosCol 0 = 2 + 1 - 1 - 2 = 0 -

For this one, I certainly didn't implement in the most optimal way. I moved the initial list into a proper List<int> structure to be able to run it backwards. Then, keep track of the max and remove the items properly. Then you move the resulting list back into the ListNode structure. There is a 3N time complexity here, plus the extra storage, but works. Code is down below, cheers, ACC. Remove Nodes From Linked List - LeetCode 2487. Remove Nodes From Linked List Medium 213 3 Add to List Share You are given the  head  of a linked list. Remove every node which has a node with a  strictly greater  value anywhere to the right side of it. Return  the  head  of the modified linked list.   Example 1: Input: head = [5,2,13,3,8] Output: [13,8] Explanation: The nodes that should be removed are 5, 2 and 3. - Node 13 is to the right of node 5. - Node 13 is to the right of node 2. - Node 8 is to the right of node 3. Example 2: Input: head = [1,1,1,1] Output: [1,1,1,1] Explanation: Ev