DEV Community: bengineer

LeetCode 350: Intersection of Two Arrays II (Ruby)

bengineer — Sun, 21 Feb 2021 19:36:01 +0000

Description: https://leetcode.com/problems/intersection-of-two-arrays-ii/

Solution

def intersect(nums1, nums2)
    result = []
    shorter = nil
    longer = nil

    shorter, longer = [nums1, nums2].sort_by &:length

    shorter.uniq.each do |n|
        shorter_count = [longer.count(n), shorter.count(n)].min
        shorter_count.times do
            result << n
        end
    end
    result
end

Bechmark

Runtime: 76 ms, faster than 28.69% of Ruby online submissions for Intersection of Two Arrays II.

Memory Usage: 209.9 MB, less than 91.80% of Ruby online submissions for Intersection of Two Arrays II.

LeetCode 917: Reverse Only Letters (Ruby)

bengineer — Sun, 21 Feb 2021 18:45:45 +0000

Description: https://leetcode.com/problems/reverse-only-letters/

Solution

def reverse_only_letters(string) # O(n)
    result = Array.new(string.length)
    letters = []

    string.each_char.with_index do |char, index|
        if is_letter?(char)
          letters << char
        else
          result[index] = char
        end
    end

    result.each_with_index do |char, index|
      result[index] = letters.pop if char == nil
    end
    result.join
end

def is_letter?(char)
    (/[a-zA-Z]/ =~ char) == 0
end

Benchmark

Runtime: 52 ms, faster than 92.31% of Ruby online submissions for Reverse Only Letters.

Memory Usage: 210.1 MB, less than 30.77% of Ruby online submissions for Reverse Only Letters.

Explanation

1- Create an array with the same amount of elements as the string we are given, and an array (stack) for the letters.

2- Iterate over each char of the string

2.1- If the char is a letter, add it to the letter stack.

2.2- If the char is not a letter, add it to the result array at the same position it was on the original string.

3- Now that our resulting array is filled with non-letters, we iterate through it; If the index we are in is nil, we pop a letter from the letters array and add it to the result array, at the current index position.

4- Join the array, so it becomes a string and return it.

LeetCode 628: Maximum Product of Three Numbers (Ruby)

bengineer — Sun, 21 Feb 2021 17:17:26 +0000

Description: https://leetcode.com/problems/maximum-product-of-three-numbers/submissions/

Solution:

def maximum_product(nums)
    nums = nums.sort
    mins_and_max = (nums[0..1] << nums[-1]).reduce(&:*)
    maxs = nums.reverse[0..2].reduce(&:*)

    if mins_and_max > maxs
        return mins_and_max
    else
        return maxs
    end
end

Explanation:

There is only two possibilities here for the maximum product:

The 3 numbers are: the greatest positive 3 numbers or
The 3 numbers are: 2 of the greatest negative numbers + 1 of the greatest positive number

Solving:

1- Sort the array.

2- Get the greatest 2 negative numbers and the greatest positive number, multiply them.

3- Get the greatest 3 positive numbers and multiply them.

4- Compare the result from step 2 and 3, return the greatest.

LeetCode 234: Palindrome Linked List (Ruby)

bengineer — Sun, 21 Feb 2021 16:58:54 +0000

Description: https://leetcode.com/problems/palindrome-linked-list/

Solution:

def is_palindrome(head)
    return true if !head
    vals = []
    node = head
    loop do
        vals << node.val
        break unless node.next
        node = node.next
    end
    vals == vals.reverse
end

Explanation:

1- Create an empty array

2- Iterate through the linked list and add its values to array created in step 1.

3- Compare the array we created with itself reversed and return.

LeetCode 520: Detect Capital (Ruby)

bengineer — Sun, 21 Feb 2021 16:48:12 +0000

Description: https://leetcode.com/problems/detect-capital/

Solution:

def detect_capital_use(word)
    (word == word.downcase) ||
    (word == word.upcase) ||
    (word == word.downcase.capitalize)
end

Explanation:

1- Check if the word is the same after converting it all to downcase.

1.2- Check if the word is the same after converting it all to upcase.

1.3- Check if the word is the same after converting it all to downcase and then converting the first character to upcase.

LeetCode 283: Move Zeroes (Ruby)

bengineer — Sun, 21 Feb 2021 16:22:14 +0000

Description: https://leetcode.com/problems/move-zeroes/

Solution:

def move_zeroes(nums)
        zeros = nums.count(0)
    nums.delete(0)
    zeros.times do
        nums << 0
    end
    nums
end

Explanation:

1- Count how many zeros there's in the array.

2- Delete all zeros from the original array.

3- Using the counter from step 1, add zeros to the end of the array.

4- Return the array.

LeetCode 703: Kth Largest Element in a Stream (Python)

bengineer — Sat, 20 Feb 2021 22:43:54 +0000

Description: https://leetcode.com/problems/kth-largest-element-in-a-stream/

Solution:

from heapq import heapify, heappush, heappop, heappushpop

class KthLargest:

    def __init__(self, k, nums):
        """
        :type k: int
        :type nums: List[int]
        """
        self.k = k
        self.k_heap = nums
        heapify(self.k_heap)
        while len(self.k_heap) > k:
            heappop(self.k_heap)

    def add(self, val):
        """
        :type val: int
        :rtype: int
        """
        if len(self.k_heap) < self.k:
            heappush(self.k_heap, val)
        else:
            heappushpop(self.k_heap, val)
        return self.k_heap[0]

Explanation:

On the initializer:

1- Create a min-heap with the stream of numbers we are given.

2- Pop from the min-heap until it has the same amount of elements as k . This means that the Kth largest element is on the top of the min-heap.

On add method:

1- If the amount of elements inside the heap is less than K , push the element to the heap. Else, push the element and then pop the top element.

2- Return the top element of the min-heap. It will be the Kth largest element.

Kids With the Greatest Number of Candies (ruby LeetCode)

bengineer — Sat, 20 Feb 2021 21:55:50 +0000

Description: https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/submissions/

Solution:

def kids_with_candies(candies, extra_candies)
    greatest = candies.max

    candies.map do |candy|
        (candy + extra_candies) >= greatest
    end
end

Explanation: A kid will have the greatest number of candies if they have the same amount or greater, than the kid that already have the most amount of candies. So the first step is to find the greatest amount of candy, among the kids and save that number. The second step is to map through the candies array and see if the selected amount, plus the extra_candies, is equal or greater than the number we saved on the first step. In the end, the function will return an array with true and/or false values.