Problem overview
This version of the uniq tool behaves like uniq -u. The method uniqOnce(lines) receives an array of strings and returns one string: the lines that are not repeated right next to themselves, joined by \n.
The key word is adjacent. A run is a stretch of equal lines that sit side by side. A line survives only when its run has length exactly 1. In the example, ["a", "a", "b", "c", "c", "c"] has three runs: two "a"s, one "b" and three "c"s. Only the run of length 1 survives, so the result is "b".
The earlier version of this tool also tracked runs; this one flips the filter and keeps a run only when it is a single line.
Approach: walk the lines and measure each run
Because only neighbours matter, the whole array can be handled in one pass without sorting or counting values globally. Two variables describe the run the loop is currently in:
prev, the text of the current run;count, how many lines the run has so far.
For each line there are two cases. If it equals prev, the run grows, so count goes up. Otherwise the previous run has just ended, and its length is final: if count is 1, the run was a lone line and goes into the result. Then the current line starts a new run with count set to 1.
A run is only judged when a different line arrives, so the last run is never judged inside the loop. It needs the same test once after the loop ends.
Step by step
- Create
result, an empty array that collects the surviving lines. - Create
countat 0. Zero means that no run has started yet. - Create
prevasnull. Together withcountit describes the current run. - Loop over the indexes of
lineswithi. - Test for a continuing run: a run exists (
count > 0) andlines[i] === prev. Both conditions are needed, and===compares the strings by value. - In the
ifbranch, add 1 tocount. - In the
elsebranch, check whether the finished run was a single line, withcount === 1. At the very first linecountis 0, so nothing is pushed. - Push
prevontoresultinside that check. - Start the next run by storing
lines[i]inprev. - Set
countto 1 for the new run. - After the loop, test the last run with the same
count === 1check, because no later line ended it. - Push
prevagain inside that check. - Return
result.join("\n"). The separator goes only between lines, so the text has no newline at the end.
The solution in JavaScript
class Solution {
uniqOnce(lines) {
let result = [];
let count = 0;
let prev = null;
for (let i = 0; i < lines.length; i++) {
if (count > 0 && lines[i] === prev) {
count++;
} else {
if (count === 1) {
result.push(prev);
}
prev = lines[i];
count = 1;
}
}
if (count === 1) {
result.push(prev);
}
return result.join("\n");
}
}
A few details are worth knowing:
nullas "no value yet".prevstarts asnull, which never equals a string, and thecount > 0test already guards the first line.- The final check matters. The last run only ends when the array does. Without the check after the loop, a lone last line would be lost.
joinbuilds the output.["a", "c"].join("\n")gives"a\nc", and an empty array gives an empty string, which is the right answer when nothing survives.- The input is not changed. The method only reads
linesand builds a new array.
Tracing the example
Here is the state after each pass of the loop for ["a", "a", "b", "c", "c", "c"], starting from count = 0, prev = null and an empty result:
| i | lines[i] | prev | count | result |
|---|---|---|---|---|
| 0 | "a" | "a" | 1 | [] |
| 1 | "a" | "a" | 2 | [] |
| 2 | "b" | "b" | 1 | [] |
| 3 | "c" | "c" | 1 | ["b"] |
| 4 | "c" | "c" | 2 | ["b"] |
| 5 | "c" | "c" | 3 | ["b"] |
At i = 0 there is no run yet, so the else branch starts one without pushing anything. At i = 1 the second "a" extends the run to length 2. At i = 2 the "b" ends the run of "a"s, whose count is 2, so nothing is pushed. At i = 3 the first "c" ends the run of "b", whose count is 1, so "b" goes into result. After the loop the last run, three "c"s, is still open. Its count is 3, so the final check pushes nothing, and the method returns "b".
Complexity
Time: O(n) for n lines. Each line is looked at once, and the pushes and the final join are linear in the output size.
Space: O(n) in the worst case, when every line survives and result holds all of them. Besides that it keeps only count and prev.
Edge cases and common mistakes
- Repeats that are not adjacent.
["a", "b", "a"]returns"a\nb\na": the two"a"s are separate runs of length 1, so both are kept. This tool does not look for duplicates across the whole input. - Everything repeated.
["a", "a", "a"]and the empty array[]both return"". - Forgetting the last run. For
["a", "a", "b"]the correct result is"b". Without the check after the loop, it would be"". - Pushing too early. Pushing a line when it first appears would also keep lines that repeat later. A run is judged only when it ends.
- Empty lines. An empty string is a line like any other:
["", "", " "]returns" ", since the two empty lines form one run of length 2. A single surviving empty line produces an empty result, just like no survivors.
Testing
["a", "a", "b", "c", "c", "c"]gives"b".["a", "b", "b", "c"]gives"a\nc".["a", "b", "b", "a"]gives"a\na".["x", "y", "z"]gives"x\ny\nz".["a", "a", "b", "b", "c"]gives"c".[]gives"".
