Maximizing the interval

Weekly Challenge 298

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Maximal Square

Task

You are given an m x n binary matrix with 0 and 1 only.

Write a script to find the largest square containing only 1's and return its area.

My solution

My main function starts by checking that the matrix has the correct number of columns for each row

def maximal_square(matrix: list[list[int]]) -> int:
    rows = len(matrix)
    cols = len(matrix[0])
    maximum_size = 0

    for row in range(rows):
        if len(matrix[row]) != cols:
            raise ValueError("Row %s has the wrong number of columns", row)

It then iterates through each cell in the matrix. If the item in that cell is a 1, it then checks the size of the square starting at that position. The max_side variable is also calculated to ensure we don't go out of bounds. We keep track of the maximum_size value and return the largest one.

    for row in range(rows):
        for col in range(cols):
            if matrix[row][col] == 1:
                max_side = min(rows-row, cols-col)
                size = find_square_from_point(matrix, row, col, max_side)
                if size > maximum_size:
                    maximum_size = size

    return maximum_size

The find_square_from_point function was frustrating to get right. I actually had a few goes before I had a solution I was happy on committing. The logic is pretty straight forward. Consider the square:

. b c d
b b c d
c c c d
d d d d

As the size of the square increases, I only need to check the bottom and right side of each square, as I know the inner part of the square has already been checked. So for the first iteration (an area of four), I check the b cells. The next iteration (area of 9), I check the c cells, and so on.

This is the code of the function:

def find_square_from_point(matrix, x: int, y: int, max_side: int) -> int:
    side = 1
    for s in range(1, max_side):
        all_ones = True
        for i in range(s+1):
            if matrix[x+i][y+s] == 0 or matrix[x+s][y+i] == 0:
                all_ones = False
                break

        if not all_ones:
            break

        side += 1

    return side ** 2

Examples

$ ./ch-1.py "[[1, 0, 1, 0, 0],[1, 0, 1, 1, 1],[1, 1, 1, 1, 1],[1, 0, 0, 1, 0]]"
4

$ ./ch-1.py "[[0, 1],[1, 0]]"
1

$ ./ch-1.py "[[0]]"
0

Task 2: Right Interval

Task

You are given an array of @intervals, where $intervals[i] = [starti, endi] and each starti is unique.

The right interval for an interval i is an interval j such that startj >= endi and startj is minimized. Please note that i may equal j.

Write a script to return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

My solution

For this task, I have a solution that works, but I'm not convinced it is the most efficient. For each interval, I set three variables:

1. The end_i value stores the end (second) value that we need to consider
2. The value lowest_j stores the lowest start value found so far (or None if not found).
3. The index_j variable stores the index of the lowest_j value, or -1 if not found.

I then have an inner loop that iterates over the intervals. If the start_j value (first value in the interval) is greater than or equal to end_i and is lower than lowest_j, I update the lowest_j and index_j values.

def right_interval(intervals: list[list[int]]) -> list:
    best_intervals = []
    for i in intervals:
        # Calculate the right interval for this interval
        end_i = i[1]
        lowest_j = None
        index_j = -1
        for j in range(len(intervals)):
            start_j = intervals[j][0]
            if start_j >= end_i:
                if lowest_j is None or start_j < lowest_j:
                    # This is the best matching interval
                    lowest_j = start_j
                    index_j = j

        best_intervals.append(index_j)

    return best_intervals

For inputs from the command line, I take a list of integers and pair them up automatically.

Examples

$ ./ch-2.py 3 4 2 3 1 2
[-1, 0, 1]

$ ./ch-2.py 1 4 2 3 3 4
[-1, 2, -1]

$ ./ch-2.py 1 2
[-1]

$ ./ch-2.py 1 4 2 2 3 4
[-1, 1, -1]