Maximum Number of Distinct Elements After Operations - Greedy w/ Sorting [JS, Java]

By on 
Description 
Solution: Greedy w/ Sorting
Sort nums in asc order.
The largest range is achieved by reducing the minimum element of nums by k.
Keep track of the current largest element we have operated on and change each nums[i] to take the next available spot within the bounds of k.
  • If it's impossible to change nums[i] into a distinct number (last + 1 >= nums[i] + k), skip it.
  • Otherwise, take the smallest possible next position: Math.max(last + 1, nums[i] - k).
    Return the number of distinct elements after the operations.
Time Complexity: O(n log(n))
Space Complexity: O(log(n))
JS
function maxDistinctElements(nums, k) {
  nums.sort((a, b) => a - b);
  let last = nums[0] - k, distinct = 1;
  for (let i = 1; i < nums.length; i++) {
    if (last + 1 > nums[i] + k) continue;
    last = Math.max(last + 1, nums[i] - k);
    distinct++;
  }
  return distinct;
};
Java
class Solution {
    public int maxDistinctElements(int[] nums, int k) {
        Arrays.sort(nums);
        int last = nums[0] - k;
        int distinct = 1;
        for (int i = 1; i < nums.length; i++) {
            if (last + 1 > nums[i] + k) continue;
            last = Math.max(last + 1, nums[i] - k);
            distinct++;
        }
        return distinct;
    }
}
Location: Auckland, New Zealand

Comments

Post a Comment

Popular posts from this blog

Beautiful Towers II - Monotonic Increasing Stack [JS]

By on
Description   Solution: Monotonic Increasing Stack Find the maximum possible sum of heights ending and starting at each index  i . left :  left[i]  = sum of heights from ( 0, ..., i ) such that they are descending from index  i  to  0 . right :  right[i]  = sum of heights from ( i, ..., n - 1 ) such that they are descending from index  i  to  n - 1 . Use a monotonic increasing stack to store indices of  maxHeights  such that they are smaller than  maxHeights[i] . left to right: We know that from index  i  to  stack[stack.length - 1] , all heights are smaller than  maxHeights[i] . Take the existing sum up to  stack[stack.length - 1]  ( left[stack[stack.length - 1]] ) and add the sum for the current range ( maxHeights[i] * (i - stack[stack.length - 1]) ) Then, do the same from right to left. Take each  maxHeights[i]  as the peak of the mountain and use the results from  ...
Read more

Check if There is a Valid Partition For The Array - Two Approaches - DP & Recursion w/ Memoization [JS]

By on
Description   Solution 1: DP - Recursion w/ Memoization Memoize each  dp(i) , where  dp(i) = whether it is possible to have a valid partition from index i to n . For each index  i , try to make it part of a valid partition (one of the three cases): Two equal elements Three equal elements Three consecutive elements Time Complexity:  O(n)  158ms Space Complexity:  O(n)  59.9MB var validPartition = function ( nums ) { let n = nums.length, memo = Array (n).fill(- 1 ); return dp( 0 ); function dp ( i ) { if (i === n) return true ; if (i === n - 1 ) return false ; if (memo[i] !== - 1 ) return memo[i]; if (nums[i] === nums[i + 1 ] && dp(i + 2 )) return memo[i] = true ; if (i < n - 2 ) { if (!dp(i + 3 )) return memo[i] = false ; let hasThreeEqual = nums[i] === nums[i + 1 ] && nums[i + 1 ] === nums[i + 2 ]; let hasThreeConsecutive = nums[i] + 1 === nums[i + 1 ] && nu...
Read more

Robot Collisions - Stack [JS]

By on
Description   Solution: Stack Note: The positions don't affect which robots will collide with each other, this stays the same no matter what. Robots adjacent to each other going right and left will always collide. In the stack, keep track of robots we have processed so far that have still survived. If the current robot is going left, We need to eliminate all right-going robots with smaller health at the top of the stack, while decreasing the health of the current robot. If the robot at the top of the stack is right-going and the health is greater, then remove the current robot and decrease the health of the robot at the top of the stack. If the robot at the top of the stack is right-going and the health is the same, remove both. If the current robot is going right, then just push it onto the stack to be dealt with later. n = number of robots Time Complexity:  O(n log(n)) Space Complexity:  O(n) var survivedRobotsHealths = function(positions, healths, directions) { let n...
Read more

Divide Nodes Into the Maximum Number of Groups - Union Find & BFS [JS]

By on
Description   Solution: Union Find & BFS Build the graph and connect nodes using union find. Find the groups of connected nodes. Find the maximum groups to divide for each connected group. Use level-by-level BFS to find the maximum depth of the group. How to detect an odd-lengthed cycle: Cycles are bound to meet in the middle since we are traversing level-by-level, so if the level of a neighbor node is equal to the current level, the cycle is odd-lengthed. n = number of nodes ,  m = number of edges Time Complexity:  O(n * (n + m))  639ms Space Complexity:  O(n + m)  64.6MB var magnificentSets = function ( n, edges ) { let uf = new UnionFind(n + 1 ); let graph = Array (n + 1 ).fill( 0 ).map( () => []); for ( let [a, b] of edges) { // 1. Build graph, connect nodes graph[a].push(b); graph[b].push(a); uf.union(a, b); } let groups = {}; for ( let i = 1 ; i <= n; i++) { // 2. Find groups of connected nodes let...
Read more

Count Elements With Maximum Frequency - Hashmap [JS]

By on
Description   Solution: Hashmap Store the counts of elements in a hashmap. Keep track of the running max frequency. If a count exceeds the max frequency, reset the total count. If a count is equal to the max frequency, add to the total count. Time Complexity:  O(n) Space Complexity:  O(n) var maxFrequencyElements = function ( nums ) { let maxFreq = 0 , countMap = {}, ans = 0 ; for ( let num of nums) { countMap[num] = (countMap[num] || 0 ) + 1 ; let count = countMap[num]; if (count > maxFreq) { ans = count; maxFreq = count; } else if (count === maxFreq) { ans += count; } } return ans; };
Read more