Constraints

• `1 <= len(paths) <= 2 * 10^4`
• Each record contains a directory followed by one or more file descriptions.
• File names and file contents contain no spaces.
• Aim for near-linear processing in the total size of the input.

Examples

Solution

def solution(paths):
    from collections import defaultdict

    content_to_paths = defaultdict(list)

    for record in paths:
        parts = record.split()
        if not parts:
            continue
        directory = parts[0]

        for file_info in parts[1:]:
            left = file_info.find('(')
            name = file_info[:left]
            content = file_info[left + 1:-1]
            full_path = directory + '/' + name
            content_to_paths[content].append(full_path)

    result = []
    for group in content_to_paths.values():
        if len(group) >= 2:
            group.sort()
            result.append(group)

    result.sort()
    return result

Time complexity: O(S + N log N), where S is the total input size and N is the total number of file paths that end up in duplicate groups. Building the map is near-linear; sorting is for deterministic output.. Space complexity: O(S), for storing parsed file paths grouped by content..

Hints

1. Use a hash map from file content to a list of full paths.
2. For each file token, split at the first `(` to get the file name, and remove the final `)` to get the content.

Constraints

• `1 <= H, W <= 2000`
• `0 <= len(operations) <= 100`
• Each pixel value is an integer.
• Each operation is either `FLIP` or `BLUR`.

Examples

Solution

def solution(img, operations):
    if not img:
        return []

    mat = [row[:] for row in img]

    def blur(matrix):
        h = len(matrix)
        w = len(matrix[0])

        prefix = [[0] * (w + 1) for _ in range(h + 1)]
        for i in range(h):
            running = 0
            for j in range(w):
                running += matrix[i][j]
                prefix[i + 1][j + 1] = prefix[i][j + 1] + running

        out = [[0] * w for _ in range(h)]
        for i in range(h):
            r1 = max(0, i - 1)
            r2 = min(h - 1, i + 1)
            for j in range(w):
                c1 = max(0, j - 1)
                c2 = min(w - 1, j + 1)
                total = (
                    prefix[r2 + 1][c2 + 1]
                    - prefix[r1][c2 + 1]
                    - prefix[r2 + 1][c1]
                    + prefix[r1][c1]
                )
                count = (r2 - r1 + 1) * (c2 - c1 + 1)
                out[i][j] = total // count

        return out

    for op in operations:
        if op == 'FLIP':
            for row in mat:
                row.reverse()
        elif op == 'BLUR':
            mat = blur(mat)

    return mat

Time complexity: O(K * H * W), where K is the number of operations. Each `FLIP` is O(H * W), and each `BLUR` is also O(H * W) using prefix sums.. Space complexity: O(H * W), mainly for the blurred image and the prefix-sum table during a blur step..

Hints

1. A horizontal flip can be done in-place by reversing each row.
2. For `BLUR`, a 2D prefix-sum table lets you compute each 3x3 neighborhood sum in O(1), making each blur pass O(H * W).