DOCSEARCHbyAlgolia
Submit Docs

ZLA Algo

website·Indexed 32 days ago

https://algo.zla.app

A collection of LeetCode problem-solving records and algorithm study notes by ZL Asica. The documentation primarily features optimized solutions implemented in Python, categorized by problem type, covering topics such as Arrays, Matrices, Two Pointers, and Sorting.

Tokens
10.2K
Snippets
33
Records
42
Agent score
50%

What's inside ZLA Algo

  1. Overview of ZL Asica's LeetCode Algorithm Documentation

    This site serves as a personal record of LeetCode problem-solving by ZL Asica. The content is categorized by problem type, primarily featuring optimized solutions implemented in Python. The documentation is built using the Docusaurus framework, with content written in Markdown and LaTeX, hosted on Cloudflare Pages.

  2. Rotate an array to the right by k steps (Problem Overview)

    The goal is to rotate an integer array nums to the right by k steps, where k is non-negative. The operation should ideally be performed in-place with O(1) extra space.

    Constraints:

    • Array length: 1 to 10^5
    • Element values: -2^31 to 2^31 - 1
    • k: 0 to 10^5

  3. Find the pivot index of an array

    The pivot index is defined as the index where the sum of all numbers strictly to the left of the index is equal to the sum of all numbers strictly to the right. If the index is on the left edge, the left sum is 0; if it is on the right edge, the right sum is 0. The goal is to return the leftmost pivot index, or -1 if no such index exists.

    Constraints:

    • Array length: 1 ≤ nums.length ≤ 10^4
    • Element values: -1000 ≤ nums[i] ≤ 1000

  4. Implement the Game of Life simulation

    The Game of Life is a cellular automaton where a grid of cells (live = 1, dead = 0) evolves based on four rules applied simultaneously to all cells:

    1. Live cell with < 2 live neighbors dies (under-population).
    2. Live cell with 2 or 3 live neighbors lives.
    3. Live cell with > 3 live neighbors dies (over-population).
    4. Dead cell with exactly 3 live neighbors becomes live (reproduction).

    Each cell interacts with its eight neighbors (horizontal, vertical, and diagonal).

  5. Rotate an n x n matrix 90 degrees clockwise in-place

    To rotate a square matrix 90 degrees clockwise without allocating another 2D matrix, you can perform a two-step transformation: first, reverse the order of the rows (vertical flip), and second, transpose the matrix (swap elements across the main diagonal). This approach ensures the operation is performed in-place with O(1) extra space and O(n²) time complexity.
    class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # Step 1: Reverse the rows (vertical flip)
        matrix[:] = matrix[::-1]

        # Step 2: Transpose the matrix
        n = len(matrix)
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

  6. Generate an n x n matrix in spiral order

    To generate an n x n matrix filled with elements from 1 to n² in spiral order, initialize an empty n x n matrix and use four boundary pointers (top, bottom, left, right) to track the current perimeter. Iterate clockwise—filling the top row, right column, bottom row, and left column—shrinking the boundaries inward after each side is completed until all cells are filled.
    class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        result = [[0 for _ in range(n)] for _ in range(n)]

        # Define four boundaries
        top, right = 0, n - 1
        left, bottom = 0, n - 1

        val = 1
        while val <= n * n:
            # Traverse top boundary from left to right
            for col in range(left, right + 1):
                result[top][col] = val
                val += 1
            top += 1  # Shrink top boundary

            # Traverse right boundary from top to bottom
            for row in range(top, bottom + 1):
                result[row][right] = val
                val += 1
            right -= 1  # Shrink right boundary

            if top <= bottom:
                # Traverse bottom boundary from right to left
                for col in range(right, left - 1, -1):
                    result[bottom][col] = val
                    val += 1
                bottom -= 1  # Shrink bottom boundary

            if left <= right:
                # Traverse left boundary from bottom to top
                for row in range(bottom, top - 1, -1):
                    result[row][left] = val
                    val += 1
                left += 1  # Shrink left boundary

        return result

  7. Implement the Plus One algorithm to increment a digit array

    The goal is to increment a large integer represented as an array of digits (where each element is a single digit from 0-9, ordered from most significant to least significant). The algorithm iterates from the end of the array to the beginning: if a digit is 9, it is set to 0 and the loop continues to the next digit (carrying the one). If a digit is less than 9, it is incremented by 1 and the process terminates. If the first digit becomes 0 after the loop, it indicates an overflow (e.g., 999 -> 000), and a 1 must be inserted at the beginning of the array.
    class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range((len(digits)), 0, -1):
            if digits[i - 1] == 9:  # Detect if digit is 9
                digits[i - 1] = 0  # If so, update to 0 (carry)
            else:
                digits[i - 1] += 1  # Otherwise, increment and stop
                break

        if digits[0] == 0: # Check for overflow (e.g., [9,9] -> [0,0])
            digits.insert(0, 1) # Insert 1 at the front

        return digits

  8. Determine the type of triangle from side lengths

    Given an array of three integers representing the sides of a triangle, determine if they can form a triangle and, if so, what type.

    Triangle Validity Rule: A triangle is valid if the sum of any two sides is greater than the third side. A common optimization is to sort the sides and check if the sum of the two shortest sides is greater than the longest side.

    Triangle Types:

    • equilateral: All three sides are of equal length.
    • isosceles: Exactly two sides are of equal length.
    • scalene: All three sides are of different lengths.
    • none: The sides cannot form a valid triangle.
    class Solution:
    def triangleType(self, nums: List[int]) -> str:
        # Sort to easily check the triangle inequality theorem
        a, b, c = sorted(nums)
        
        # Check if it can form a triangle: sum of two shortest sides must be > longest side
        if a + b <= c:
            return "none"

        # Use a set to count unique side lengths
        unique_sides = len(set(nums))
        
        if unique_sides == 1:
            return "equilateral"
        elif unique_sides == 2:
            return "isosceles"
        else:
            return "scalene"

  9. Find the maximum number of consecutive ones in a binary array

    Given a binary array nums, the goal is to return the maximum number of consecutive 1s. The constraints are that the array length is between 1 and 10^5, and each element is either 0 or 1.
    # Example 1
Input: nums = [1,1,0,1,1,1]
Output: 3

# Example 2
Input: nums = [1, 0, 1, 1, 0, 1]
Output: 2

  11. Arrange an array of integers to form the smallest possible concatenated string

    To form the smallest possible number by concatenating a list of non-negative integers, a greedy sorting approach is used. Instead of standard numerical sorting, elements $a$ and $b$ are compared based on their concatenated results: if the string concatenation of $a+b$ is smaller than $b+a$, then $a$ should precede $b$ in the final sequence. This ensures the resulting string is lexicographically smallest. The final result should be returned as a string to handle large numbers and preserve leading zeros.
    from functools import cmp_to_key
from typing import List

class Solution:
    def crackPassword(self, password: List[int]) -> str:
        # Use cmp_to_key to implement a custom sorting rule
        sorted_password = sorted(password, key=cmp_to_key(self.compare))
        # Join sorted integers into a single string
        return ''.join(str(i) for i in sorted_password)

    def compare(self, a: int, b: int) -> int:
        # Custom comparator: compare concatenated strings of a+b and b+a
        if int(str(a) + str(b)) < int(str(b) + str(a)):
            return -1
        return 1

  12. Solve 'Product of Array Except Self' using Prefix and Suffix Products

    To find the product of all elements in an array except the element at index i without using division, you can calculate the product of all elements to the left (prefix product) and all elements to the right (suffix product) of index i. The result for answer[i] is the product of the prefix product and the suffix product at that position.

    Algorithm steps:

    1. Initialize an output array answer of the same length as the input array, filled with 1s.
    2. Iterate forward through the array to calculate the prefix product for each element and store it in answer[i].
    3. Iterate backward through the array to calculate the suffix product and multiply it into the existing value in answer[i].

    This approach ensures O(n) time complexity and O(1) extra space complexity (excluding the output array).

    class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n

        # Calculate prefix products
        prefix = 1
        for i in range(n):
            answer[i] = prefix
            prefix *= nums[i]

        # Calculate suffix products and multiply with existing prefix products
        suffix = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]

        return answer