1351 Count Negative Numbers in a Sorted Matrix.rtf

{\rtf1\ansi\ansicpg1252\cocoartf2706
\cocoatextscaling0\cocoaplatform0{\fonttbl\f0\fnil\fcharset0 .SFNS-Regular_wdth_opsz120000_GRAD_wght1F40000;\f1\fnil\fcharset0 Menlo-Regular;}
{\colortbl;\red255\green255\blue255;\red29\green29\blue29;\red255\green255\blue255;\red0\green0\blue255;
\red0\green0\blue0;\red32\green108\blue135;\red101\green76\blue29;\red0\green0\blue109;\red19\green118\blue70;
\red157\green0\blue210;\red15\green112\blue1;}
{\*\expandedcolortbl;;\cssrgb\c14902\c14902\c14902;\cssrgb\c100000\c100000\c100000;\cssrgb\c0\c0\c100000;
\cssrgb\c0\c0\c0;\cssrgb\c14902\c49804\c60000;\cssrgb\c47451\c36863\c14902;\cssrgb\c0\c6275\c50196;\cssrgb\c3529\c52549\c34510;
\cssrgb\c68627\c0\c85882;\cssrgb\c0\c50196\c0;}
\margl1440\margr1440\vieww11520\viewh8400\viewkind0
\deftab720
\pard\pardeftab720\partightenfactor0

\f0\fs36 \cf2 \cb3 \expnd0\expndtw0\kerning0
\outl0\strokewidth0 \strokec2 1351\'a0Count Negative Numbers in a Sorted Matrix
\f1\fs26 \cf4 \cb3 \strokec4 \
\pard\pardeftab720\partightenfactor0
\cf4 class\cf0 \strokec5  \cf6 \strokec6 Solution\cf0 \strokec5 :\cb1 \
\pard\pardeftab720\partightenfactor0
\cf0 \cb3     \cf4 \strokec4 def\cf0 \strokec5  \cf7 \strokec7 countNegatives\cf0 \strokec5 (\cf8 \strokec8 self\cf0 \strokec5 , \cf8 \strokec8 grid\cf0 \strokec5 : List[List[\cf6 \strokec6 int\cf0 \strokec5 ]]) -> \cf6 \strokec6 int\cf0 \strokec5 :\cb1 \
\cb3         ROWS = \cf7 \strokec7 len\cf0 \strokec5 (grid)\cb1 \
\cb3         COLS = \cf7 \strokec7 len\cf0 \strokec5 (grid[\cf9 \strokec9 0\cf0 \strokec5 ])\cb1 \
\cb3         count = \cf9 \strokec9 0\cf0 \strokec5  \cb1 \
\
\cb3         \cf10 \strokec10 for\cf0 \strokec5  row \cf4 \strokec4 in\cf0 \strokec5  \cf7 \strokec7 range\cf0 \strokec5 (ROWS):\cb1 \
\cb3             l,r = \cf9 \strokec9 0\cf0 \strokec5 , COLS-\cf9 \strokec9 1\cf0 \cb1 \strokec5 \
\cb3             \cf10 \strokec10 while\cf0 \strokec5  l<=r:\cb1 \
\cb3                 mid = (l+r)//\cf9 \strokec9 2\cf0 \cb1 \strokec5 \
\
\cb3                 \cf10 \strokec10 if\cf0 \strokec5  grid[row][mid]>=\cf9 \strokec9 0\cf0 \strokec5 :\cb1 \
\cb3                     l = mid+\cf9 \strokec9 1\cf0 \cb1 \strokec5 \
\cb3                 \cb1 \
\cb3                 \cf10 \strokec10 if\cf0 \strokec5  grid[row][mid]<\cf9 \strokec9 0\cf0 \strokec5 :\cb1 \
\cb3                     \cf10 \strokec10 while\cf0 \strokec5  grid[row][mid-\cf9 \strokec9 1\cf0 \strokec5 ]<\cf9 \strokec9 0\cf0 \strokec5  \cf4 \strokec4 and\cf0 \strokec5  (mid-\cf9 \strokec9 1\cf0 \strokec5 )>=l:\cb1 \
\cb3                         mid=mid-\cf9 \strokec9 1\cf0 \cb1 \strokec5 \
\cb3                     count+=(COLS-mid)\cb1 \
\cb3                     \cf10 \strokec10 break\cf0 \cb1 \strokec5 \
\cb3         \cb1 \
\
\cb3             \cf11 \strokec11 # for c in range(COLS-1,-1,-1):\cf0 \cb1 \strokec5 \
\cb3             \cf11 \strokec11 #     if grid [r][c] < 0:\cf0 \cb1 \strokec5 \
\cb3             \cf11 \strokec11 #         count+=1\cf0 \cb1 \strokec5 \
\cb3             \cf11 \strokec11 #     else:\cf0 \cb1 \strokec5 \
\cb3             \cf11 \strokec11 #         break\cf0 \cb1 \strokec5 \
\cb3         \cb1 \
\cb3         \cf10 \strokec10 return\cf0 \strokec5  count \cb1 \
\
\cb3         \cf11 \strokec11 #O(m*n)\cf0 \cb1 \strokec5 \
}