Questions
========================================


Spiral Matrix
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. only:: html

    `Link <https://leetcode.com/problems/spiral-matrix/>`_


Print a matrix in spiral order

.. figure:: spiral_matrix.png
    :name: spiral_matrix
    :scale: 80%

Solution:

.. literalinclude:: ./spiral_matrix.h
    :language: c++
    :linenos:


Young Tableau
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Sorted matrix can be considered as extension of sorted array, or a binary search tree with root in bottom left or top right corner. It is sorted not only in each row and column, but also in main diagonal.



Rotate Image/Matrix
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^



Pascal Triangle
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Solution:

.. literalinclude:: ./pascal.h
    :language: c++
    :linenos:

you can use `Spiral Matrix`_.

Minimum Time Interval
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

.. code-block:: none

    [Google Phone Screen] Given a string list, where each element in it is a timestamp, and the format is: "hh:mm", for example: ["23:23","11:13","21:01","01:03" ], returns the smallest time interval between two elements.

    Algorithm time complexity should be better than O(NLogN).

----

We can use a 24x60 bool matrix as the bucket for ``bucket sort``.

.. literalinclude:: min_time_interval_test.cpp
    :language: c++
    :lines: 4-29
    :linenos:

.. only:: html

    - https://leetcode.com/problems/minimum-time-difference/
    - https://www.1point3acres.com/bbs/thread-868755-1-1.html


Minimum Flip
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Given a matrix m with red(1) and blue(0) squares in it, you can **only flip the top left square m[0][0]** but there is a **chain reaction**, which is all the adjacent(up,down,left,right) squares of the same color are flipped accordingly.

Question: After how many flips, you can make all squares one color? Can you write a function to calculate it?

.. code-block:: none

  Example 1:

  [0, 0, 1, 0]     flip     [1, 1, 1, 0]     flip     [0, 0, 0, 0]    flip    [1, 1, 1, 1]
  [0, 1, 0, 1]   ------->   [1, 1, 0, 1]   ------->   [0, 0, 0, 1]  ------->  [1, 1, 1, 1]
  [0, 1, 0, 1]              [1, 1, 0, 1]              [0, 0, 0, 1]            [1, 1, 1, 1]

  Output: 3

  Example 2:

  [0, 0, 1, 0]     flip     [1, 1, 1, 0]     flip     [0, 0, 0, 0]
  [0, 0, 0, 1]   ------->   [1, 1, 1, 1]   ------->   [0, 0, 0, 0]
  [0, 1, 0, 1]              [1, 1, 1, 1]              [0, 0, 0, 0]

  Output: 2

Can you make your algorithm having time complexity: O(R*C)

----

.. literalinclude:: code/min_flip_test.cpp
    :language: c++
    :linenos:


.. only:: html

    - https://www.1point3acres.com/bbs/thread-889468-1-1.html