Tuesday, October 27, 2015

algo IV: binary matrix { raiserchu

Q: Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. See raiserchu's mail on 12 Sep 13.

Analysis: Each rectangle is identified by 2 vertices, i.e 4 integers. Without loss of generality, We require the "high" corner to have higher x-coordinate and higher y-coordinate than the "low" corner. (We can assume y-axis run upward.) With this nested loop we can iterate over all possible rectangles in a given matrix:

Lock low corner
Move high corner in typewriter (zigzag) steps i.e.
  hold highY and move highX
  process the resulting rectangle
  increment highY and repeat
Move the lower corner in typewriter steps and repeat

Key observation: any "bad pixel" disqualifies every rectangle containing it.

--- My solution 2:
1) Save all bad pixels in SQL table Bad, 
indexed by x-coordinate and 
indexed by y-ordinate

Table can be in-memory like Gemfire. Many sorted maps (skiplist or RB tree) support range selection. Gelber interviewer showed me how to use a SQL table to solve algo problems.

2) Follow the nested loop to iterate over all possible rectangles, either disqualify it or save/update its area in maxFound. Here's how to disqualify efficiently:

For each rectangle under evaluation, we have 4 numbers (lowX, lowY) and (highX, highY).

select ANY from Bad where lowX < Bad.x < highX and lowY < Bad.y < highY

If any hit, then rectangle disqualified. In fact all high corners at the same horizontal level disqualify, so in the nested loop we skip ahead to increment highY

3) At end of nested loop, maxFound is the final answer.
--- my earlier solution 1:
1) Iterate over all possible rectangles and save them in a SQL table Rec, indexed by the 4 integers. No need to validate each (time-consuming). Next we start elimination
2) Iterate over all bad pixels. For each bad pixel found, delete from Rec where Rec.lowX < X < Rec.highX and Rec.lowY < Y < Rec.highY

Now all remaining rows are valid candidates
3) max ( (x2 - x1)*(y2 - y1) )
--- Here's my partial solution:
We can effectively ignore all the "good pixels".

1) Look at the x coordinates of all bad pixels. Sort them into an array. Find the largest gap. Suppose it's between x=22 and x=33. Our candidate rectangle extends horizontally from 23 to 32, exactly. Notice there's no bad pixel within this vertical band [1].
2) Look at the y coordinates of all bad pixels. Sort them into an array. Find the largest gap. Suppose it's between y=15 and y=18. Our candidate rectangle extends vertically from 16 to 17, exactly.
[1] This candidate rectangle can expand All the way vertically, though it may give a bigger rectangle
Ditto horizontally.

No comments:

Total Pageviews

my favorite topics (labels)

_fuxi (302) _misLabel (13) _orig? (3) _rm (2) _vague (2) clarified (58) cpp (39) cpp_const (22) cpp_real (76) cpp/java/c# (101) cppBig4 (54) cppSmartPtr (35) cppSTL (33) cppSTL_itr (27) cppSTL_real (26) cppTemplate (28) creditMkt (14) db (65) db_sybase (43) deepUnder (31) dotnet (20) ECN (27) econ/bank` (36) fin/sys_misc (43) finGreek (34) finReal (45) finRisk (30) finTechDesign (46) finTechMisc (32) finVol (66) FixedIncom (28) fMath (7) fMathOption (33) fMathStoch (67) forex (39) gr8IV_Q (46) GTD_skill (15) GUI_event (30) inMemDB (42) intuit_math (41) intuitFinance (57) javaMisc (68) javaServerSide (13) lambda/delegate (22) marketData (28) math (10) mathStat (55) memIssue (8) memMgmt (66) metaProgram` (6) OO_Design (84) original_content (749) polymorphic/vptr (40) productive (21) ptr/ref (48) py (28) reflect (8) script`/unix (82) socket/stream (39) subquery/join (30) subvert (13) swing/wpf (9) sysProgram` (16) thread (164) thread_CAS (15) thread_cpp (28) Thread* (22) timeSaver (80) transactional (23) tune (24) tuneDB (40) tuneLatency (30) z_ajax (9) z_algoDataStruct (41) z_arch (26) z_arch_job (27) z_automateTest (17) z_autoTrad` (19) z_bestPractice (39) z_bold (83) z_bondMath (35) z_book (18) z_boost (19) z_byRef^Val (32) z_c#GUI (43) z_c#misc (80) z_cast/convert (28) z_container (67) z_cStr/arr (39) z_Favorite* (8) z_FIX (15) z_forex (48) z_fwd_Deal (18) z_gz=job (33) z_gzBig20 (13) z_gzMgr (13) z_gzPain (20) z_gzThreat (19) z_hib (19) z_IDE (52) z_ikm (5) z_IR_misc (36) z_IRS (26) z_javaWeb (28) z_jdbc (10) z_jobFinTech (46) z_jobHunt (20) z_jobRealXp (10) z_jobStrength (15) z_jobUS^asia (27) z_letter (42) z_linq (10) z_memberHid` (11) z_MOM (54) z_nestedClass (5) z_oq (24) z_PCP (12) z_pearl (1) z_php (20) z_prodSupport (7) z_py (31) z_quant (14) z_regex (8) z_rv (38) z_skillist (48) z_slic`Problem (6) z_SOA (14) z_spring (25) z_src_code (8) z_swingMisc (50) z_swingTable (26) z_unpublish (2) z_VBA/Excel (8) z_windoz (17) z_wpfCommand (9)

About Me

New York (Time Square), NY, United States
http://www.linkedin.com/in/tanbin