Katkat
Back

Implement in-place duplicate removal

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates proficiency in in-place array manipulation, handling duplicates in sorted sequences, and formal reasoning about space and time complexity.

Given a non-decreasing array of integers, overwrite it in-place so that each distinct value appears exactly once while preserving the order of the unique values. Return the new length of the compressed prefix and justify that your algorithm uses O(

  1. extra space and runs in O(n) time. Follow-up: modify your solution so that each value may appear at most twice, and explain the changes.