All problems

Matching Photo Frames

Medium · hash map

A framing shop has a pile of picture frames. Frame i is frames[i] = [width, height], in whole millimetres.

Two frames have the same shape if one is an exact enlargement of the other, once you are allowed to turn a frame a quarter turn. For example, a 4 x 6 frame, a 6 x 4 frame and a 2 x 3 frame all have the same shape, but a 3 x 4 frame does not.

Sort the frames into groups of the same shape. Return a list of groups. Each group is a list of frame indices in increasing order, and the groups are ordered by the smallest index they contain.

Examples

Example 1

Input: frames = [[4, 6], [6, 4], [2, 3], [10, 5], [1, 2], [3, 9]]

Output: [[0, 1, 2], [3, 4], [5]]

The first three are all 2 : 3, the next two are 1 : 2, and the last one is 1 : 3.

Example 2

Input: frames = [[5, 5], [1, 1], [2, 2]]

Output: [[0, 1, 2]]

All squares have the same shape.

Constraints