[PYTHON] Let Code Day52 Starting from Zero "1351. Count Negative Numbers in a Sorted Matrix"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

Apparently, many engineers take measures on the site called LetCode.

It is a site that trains the algorithmic power that can withstand the coding test that is being done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.

I wrote it in a big way, but I have no plans to have such an interview at the moment.

However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

I'm solving it with Python3.

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day51 "647. Palindromic Substrings" starting from zero

Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.

Twitter I'm doing it.

problem

1351. Count Negative Numbers in a Sorted Matrix

The difficulty level is Easy.

Given the matrix grid of m * n. Both the rows and columns are sorted in a format that does not cause an increase. (That is, the element values are maintained or decreased in that order.)

The problem is to design an algorithm that returns the negative numbers that exist in that grid.

Example 1:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] Output: 8 Explanation: There are 8 negatives number in the matrix.

Example 2:

Input: grid = [[3,2],[1,0]] Output: 0 Example 3:

Example 3: Input: grid = [[1,-1],[-1,-1]] Output: 3

Example 4:

Input: grid = [[-1]] Output: 1

solution

import itertools

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        count = 0
        lists = []
        lists = list(itertools.chain.from_iterable(grid))
        for i in lists:
            if i < 0:
                count += 1
        return count
# Runtime: 128 ms, faster than 63.80% of Python3 online submissions for Count Negative Numbers in a Sorted Matrix.
# Memory Usage: 14.9 MB, less than 20.02% of Python3 online submissions for Count Negative Numbers in a Sorted Matrix.

It is like this. Well, I think you can imagine turning each element with a for statement for the time being.

However, some people may not be so familiar with ʻitertools.chain.from_iterable`. Is it not?

Another constructor for chain (). Receives chained input from one iterable argument that is lazy evaluated. This function is roughly equivalent to the code below:

def from_iterable(iterables): # chain.from_iterable(['ABC', 'DEF']) --> A B C D E F for it in iterables: for element in it: yield element

 As you can see in the official documentation, it works as above.
 By the way, chain () has the following explanation.

>
itertools.chain(*iterables)
 Create an iterator that returns all elements of the first iterable, then all elements of the second iterable, and all elements of iterable. It is used when treating consecutive sequences as one sequence. Approximately equivalent to:

> ```Python
def chain(*iterables):
    # chain('ABC', 'DEF') --> A B C D E F
    for it in iterables:
        for element in it:
            yield element

What's the difference! May be, but Introduction of chain, chain.from_iterable (to master python's itertools) It is well explained in this article, and I will introduce it because it is faster to refer to it.

The good thing about Python is that you can enjoy it.

To change the story, I participated in a Python study session (held online). I participated in the study session for the first time in a long time, so it was more fun and the update was delayed. I'm planning to write an article about that (probably Sphinx), so please have a look.

Up to here for this time. Thank you for your hard work.