The Bucket Sort algorithm

LC75 - example of Sorting Colors

The problem statement is as below.

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color 
are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # bucket sort 
        value_range = 3 #red, white or blue
        counts = [0] * value_range

        for i, n in enumerate(nums):
            counts[n] += 1

        i = 0
        for value, freq in enumerate(counts):
            print(value, freq)  
            for _ in range(freq):
                nums[i] = value
                i += 1

Quick rundown

The bucket sort algorithm relies on the fact that values belong to a known range. In this example it is [0,2] ∈ Z. The input arrays have already been prepared, by encoding categorical values into numerical ones. The same thing could be said about a different numerical range where the start of range is re-indexed or shifted back to 0.

LC765 - Couples holding hands

Problem Statement

There are n couples sitting in 2n seats arranged in a row and want to hold hands.
The people and seats are represented by an integer array row where row[i] is the ID of the person sitting in the ith seat. 
The couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), 
and so on with the last couple being (2n - 2, 2n - 1).

Return the minimum number of swaps so that every couple is sitting side by side. 
A swap consists of choosing any two people, then they stand up and switch seats.

Initial solution

The below solution provides an O(n) time complexity and memory. Relatively simply, checking for every pair of people, if the left-hand side person is not seated next to its beloved, then we swap the right person next to them.

Automated Vulnerability Scanning for Dependencies & Packages

Do we need to explain why?

🔥💥💣🚨⚡☠️🧨

That’s what I thought.

Configure your pipeline with Snyk

There is a plethora of tools available out there for security scans and/or vulnerable dependencies - Dependabot, Trivy, sonarQube/Lint, Anchore, etc. Most of which can be integrated into your IDE or CI/CD.

For this use case, Snyk has been selected. Snyk is able to scan code, open-source dependencies, container images, and infrastructure as code configurations to helps developers prioritize and fix security vulnerabilities. The free version comes with a max limit scans per month.