Number of Distinct Islands


  • 0

    Click here to see the full article post


  • 0
    J

    For example, if an island is made from squares [(2, 3), (2, 4), (3, 4)], we can think of this shape as [(0, 0), (0, 1), (1, 0)] when anchored at the top-left corner.

    Should be [(0, 0), (0, 1), (1, 1)]


  • 0
    K

    Why do you have "shape.add(0);" in the function explore of the second approach?


  • 0
    K

    Can you explain how you converted our tuples (r - r0, c - c0) to integers in the Java solution? I don't quite understand.


  • 0

    @kk636 I think the reason for "shape.add(0)" is, as the author pointed out, a way to indicate when we exit from the explore function. The initial call marks the entering of the function after all.


  • 0
    This post is deleted!

  • 0

    @jwgoh Corrected, thanks.

    @kk636 (shape.add(0))
    Say we have shapes like

    A = [[1,0],
         [1,1]]
    B = [[1,1],
         [1,0]]
    

    Without shape.add(0), which records when we exit the function, these two shapes have the same path signature of [0, 1, 3]. This is because we don't know whether the east ("3") direction marked in the shape means east of the top left corner, or east of the bottom left corner.

    When we record exiting the function, they will have the signature [0, 1, 3, 0, 0, 0] and [0, 1, 0, 3, 0, 0] respectively. The 0 basically functioned as an "escape" or "backwards" move when describing the path - it says take the cursor that you have, and go back to the square you were on. We could interpret these path signatures as [SOUTH, EAST, ESCAPE, ESCAPE, ESCAPE], and [SOUTH, ESCAPE, EAST, ESCAPE, ESCAPE] if we wanted to reconstruct the path.

    @kk636 ((r - r0, c - c0) tuples)

    We need to convert these tuples to an integer with any injective function (injective just means two different tuples don't convert to the same integer.)

    Typically, the function that people might choose is (r, c) -> (r * num_columns + c). This is because they can take that result V and inspect V // num_columns, V % num_columns to reconstruct the answer. Instead of choosing the constant num_columns, we could have chosen any bigger number as well.

    Here, because we are dealing with local coordinates, c >= 0 is not guaranteed: it could be anywhere inside the interval [-num_columns + 1, num_columns - 1]. However, r >= 0 is guaranteed because of how we found the shape (we looked for land from top to bottom, left to right.)

    In the end, we chose the function (r, c) -> (r * (2 * num_columns) + c). No two local coordinates will have the same result, which is all we needed.


  • 0
    K

    @awice Thank you for your great explanation. However, when I tested on my code using BFS, and (r, c) -> (r * num_columns + c), it passed all the test cases.


  • 0

    @kk636 It would fail this case, which has now been added.

    [[1, 1, 1, 1], #0123
     [1, 0, 1, 0], #4 6
     [0, 0, 0, 0],
     [0, 1, 1, 1], # 012
     [1, 1, 0, 1]] #34 6
    

  • 0
    K
    This post is deleted!

  • 0

    @kk363 It's wrong in 3 spots. First, you multiply by numRow, but instead you should multiply by numCol. If numRow is say, 2, it can cause major problems. Secondly, you concatenate a string without a delimiter. So if the 'injective' function returns "23", that could be formed by "2" + "3" in another shape. Third, you don't multiply by 2 * numCol, an example bad testcase would be [[0, 0, 1, 1, 1], [1, 1, 1, 0, 0], [0, 0, 0, 0, 0], [0, 1, 1, 1, 1], [1, 1, 0, 0, 0]].


  • 1
    G

    Why is the time complexity O(R * C)?
    Here each "add" operation should firstly check if there is a duplicate exists, then execute it. But "shape" is a hashset(arraylist) here, can we still achieve an O(1) look-up even if the element of a hashset is another type of container?

    if (!shape.isEmpty()) {
                        shapes.add(shape);
                    }
    

  • 0

    @Geminiiiiii The total amount of information content in all shapes is O(R*C).


  • 0

    @awice Not sure how that's supposed to answer the question. Sounds more like a justification for O(R*C) space rather than for O(R*C) time.


  • 0

    @ManuelP @Geminiiiiii For each shape, we have to iterate through it in order to determine the hash. The sum of such iterations is O(R*C). If it helps, you can think of our algorithm as hashing some string representation of the shape instead.


  • 0

    @awice Calculating the hash is not the only reason for iterating a shape. If the hash matches, you're then also iterating to compare the actual shapes. So if you had many hash collisions, you'd iterate the new shape many times.


  • 0
    S

    for approach 1, how come the local row-coordinate could be negative? if you scan the grid row by row , it's not necessary to multiply by that additional 2 I think.


  • 0

    @seanzhou1023 The row is guaranteed non-negative. The local column isn't, like in this shape:

    _X
    XX
    

  • 0
    S

    Finally got why need to multiply additional 2. It's not because local row-coordinate could be negative, it's because the local column-coordinate could be negative. Brilliant Idea~


  • 0
    S

    @awice exactly, thanks for the explanation :) Excellent~


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.