The Weekly Challenge 068

Zero Matrix and Reorder List

Solutions on GitHub

Task 1: Zero Matrix

If an element in an M x N matrix is 0, set its entire row and column to 0.

Example Output

Input: [1, 0, 1] [1, 1, 1] Output: [0, 0, 0] [1, 0, 1]

Logic

Scan matrix to record row and column indices containing zero, then update target rows and columns.

Perl Solution

ch-1.pl

sub zero_matrix { my ($matrix) = @_; my (%rows, %cols); for my $r (0 .. $#$matrix) { for my $c (0 .. $#{$matrix->[$r]}) { if ($matrix->[$r][$c] == 0) { $rows{$r} = $cols{$c} = 1; } } } for my $r (keys %rows) { @{$matrix->[$r]} = (0) x @{$matrix->[$r]}; } for my $c (keys %cols) { for my $r (0 .. $#$matrix) { $matrix->[$r][$c] = 0; } } }

Python Solution

ch-1.py

def zero_matrix(matrix: List[List[int]]) -> None: rows, cols = set(), set() for r in range(len(matrix)): for c in range(len(matrix[0])): if matrix[r][c] == 0: rows.add(r); cols.add(c) for r in rows: for c in range(len(matrix[0])): matrix[r][c] = 0 for c in cols: for r in range(len(matrix)): matrix[r][c] = 0

Task 2: Reorder List

Reorder linked list L0 -> L1 -> ... -> Ln-1 -> Ln as L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 ...

Example Output

Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 1 -> 5 -> 2 -> 4 -> 3

Logic

Find midpoint of linked list, reverse second half, and interleave nodes from first and second half.

Perl Solution

ch-2.pl

sub reorder_list { my ($head) = @_; my @nodes; my $curr = $head; while ($curr) { push @nodes, $curr; $curr = $curr->{next}; } my ($i, $j) = (0, $#nodes); while ($i < $j) { $nodes[$i]->{next} = $nodes[$j]; $i++; break if $i == $j; $nodes[$j]->{next} = $nodes[$i]; $j--; } $nodes[$i]->{next} = undef; }

Python Solution

ch-2.py

def reorder_list(head: Optional[ListNode]) -> None: nodes = [] curr = head while curr: nodes.append(curr) curr = curr.next i, j = 0, len(nodes) - 1 while i < j: nodes[i].next = nodes[j] i += 1 if i == j: break nodes[j].next = nodes[i] j -= 1 if nodes: nodes[i].next = None