Compress vertices into uniques and indices

Q: Compress vertices into uniques and indices

This question evaluates a candidate's ability to perform duplicate detection and compression of sequences of fixed-length tuples, exercising skills in data structures, mapping/hash concepts, array manipulation, and preserving first-seen ordering.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

You are given an array of vertices (a 2D array). Each vertex may repeat. Implement a simple “compression” that produces:

unique_vertices : the list of unique vertices, preserving the order of first appearance .
indices : for each vertex in the original array, the index of its corresponding vertex in unique_vertices .

Input

vertices : a list of n vertices
each vertex is a fixed-length list/tuple of integers (e.g., 3D vertex)

Output

unique_vertices : list of unique vertices in first-seen order
indices : integer list of length n

Example

Input:

[[2,2,2], [0,1,0], [2,1,2], [0,1,0]]

Output:

unique_vertices = [[2,2,2], [0,1,0], [2,1,2]]
indices         = [0, 1, 2, 1]

Notes / Constraints

Treat two vertices as equal if all coordinates match.
Aim for efficient time complexity (better than O(n^2) if possible).

Compress vertices into uniques and indices

Quick Overview

Input

Output

Example

Notes / Constraints

Comments (0)