go-01-unique

# Unique preserving order

Implement **`solution.go`** in `package challenge` exporting:

```go
func Unique(xs []int) []int
```

Return a new slice containing the elements of `xs` with duplicates removed, keeping each value at
the position of its **first occurrence**.

Rules:

- Preserve **first-occurrence order** — do not sort the result.
- Each distinct value appears exactly once.
- Do **not** mutate the input slice.
- For an empty (or nil) input, return an **empty, non-nil** slice (length 0).

Examples:

```go
Unique([]int{3, 1, 3, 2, 1}) // => [3, 1, 2]
Unique([]int{1, 2, 3})       // => [1, 2, 3]
Unique([]int{5, 5, 5})       // => [5]
Unique([]int{})              // => [] (non-nil, length 0)
```

package challenge

import (
	"reflect"
	"testing"
)

func TestUnique(t *testing.T) {
	cases := []struct {
		name string
		in   []int
		want []int
	}{
		{"removes duplicates preserving order", []int{3, 1, 3, 2, 1}, []int{3, 1, 2}},
		{"already unique unchanged", []int{1, 2, 3}, []int{1, 2, 3}},
		{"all same collapses to one", []int{5, 5, 5}, []int{5}},
		{"empty returns empty", []int{}, []int{}},
		{"single element", []int{42}, []int{42}},
		{"negatives and zero", []int{0, -1, 0, -1, 2}, []int{0, -1, 2}},
	}
	for _, tc := range cases {
		t.Run(tc.name, func(t *testing.T) {
			got := Unique(tc.in)
			if !reflect.DeepEqual(got, tc.want) {
				t.Errorf("Unique(%v) = %v, want %v", tc.in, got, tc.want)
			}
		})
	}
}

func TestUniqueReturnsNonNil(t *testing.T) {
	if Unique([]int{}) == nil {
		t.Error("Unique should return a non-nil slice for empty input")
	}
	if Unique(nil) == nil {
		t.Error("Unique should return a non-nil slice for nil input")
	}
}

func TestUniqueDoesNotMutateInput(t *testing.T) {
	in := []int{1, 1, 2}
	_ = Unique(in)
	if !reflect.DeepEqual(in, []int{1, 1, 2}) {
		t.Errorf("input was mutated: got %v", in)
	}
}

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

To solve this problem, we need to implement a function that takes a slice of integers and returns a new slice with duplicates removed, keeping only the first occurrence of each element. The order of elements in the result must be the same as their first occurrence in the input slice.

### Approach
1. **Check for Nil Input**: If the input slice is nil, return an empty slice immediately.
2. **Track Seen Elements**: Use a map to keep track of elements that have already been encountered. This helps in efficiently checking for duplicates.
3. **Build Result Slice**: Iterate through each element of the input slice. For each element, if it has not been seen before, add it to the result slice and mark it as seen in the map.
4. **Return Result**: After processing all elements, return the result slice which contains only the first occurrences of each element.

### Solution Code
```go
package challenge

func Unique(xs []int) []int {
    if xs == nil {
        return []int{}
    }
    seen := make(map[int]bool)
    result := []int{}
    for _, num := range xs {
        if !seen[num] {
            seen[num] = true
            result = append(result, num)
        }
    }
    return result
}
```

### Explanation
- **Nil Check**: The function first checks if the input slice is nil. If it is, an empty slice is returned immediately to handle this edge case.
- **Map Usage**: A map is used to track which elements have been added to the result slice. This allows for O(1) average time complexity for both checking and inserting elements.
- **Iteration and Result Construction**: The function iterates over each element in the input slice. For each element, it checks if it has been seen before using the map. If not, the element is added to the result slice and marked as seen.
- **Efficiency**: This approach ensures that each element is processed exactly once, leading to an overall time complexity of O(n), where n is the length of the input slice. The space complexity is also O(n) in the worst case, where all elements are unique.

This solution efficiently handles all edge cases, including nil and empty input slices, while preserving the order of first occurrences and removing duplicates.

Okay, I need to solve this problem where I have to write a Go function called Unique that takes a slice of integers and returns a new slice with duplicates removed, keeping only the first occurrence of each element. Hmm, let's think about how to approach this.

So, the function signature is given: func Unique(xs []int) []int. The input is a slice, and I can't mutate it. So I need to create a new slice. The output should preserve the order of the first occurrences and remove any duplicates that come after.

Let me think about the steps. I need to iterate through each element in the input slice. For each element, I check if I've seen it before. If I haven't, I add it to the result slice and mark it as seen. If I have, I skip it.

How do I keep track of the elements I've already added? I can use a map to store the elements as keys. Since Go maps can't have duplicate keys, this will help me track which elements have been added.

Wait, but the order is important. So I can't just collect all unique elements and then sort them because the problem says to preserve the first-occurrence order. So the order in the result must be the same as the order in which elements first appeared in the input.

So the plan is:

1. Initialize an empty map to keep track of elements we've already added.
2. Initialize an empty slice to build the result.
3. Iterate over each element in the input slice:
   a. For the current element, check if it's in the map.
   b. If it's not in the map, add it to the result slice and mark it in the map.
   c. If it is in the map, skip it.
4. After processing all elements, return the result slice.

Wait, but what about the case when the input is nil? Oh, the problem says that for an empty or nil input, return an empty, non-nil slice of length 0. So in Go, if xs is nil, we should return an empty slice, not nil. So I need to handle that case.

So first, I should check if xs is nil. If it is, return an empty slice. Or wait, in Go, if the input is nil, the function will receive a nil slice, and we need to return an empty slice. So in code, perhaps:

if xs == nil {
    return []int{}
}

Wait, but in Go, if you pass a nil slice to a function expecting []int, it's allowed. So the function can handle it.

So, let's outline the code:

func Unique(xs []int) []int {
    if len(xs) == 0 {
        return []int{} // Or just return nil? Wait, no, the problem says to return an empty, non-nil slice. So for empty input, return a slice with length 0, not nil. So in Go, when the input is nil, we should return an empty slice. Wait, no: the problem says for empty or nil input, return an empty, non-nil slice. So if xs is nil, return an empty slice (length 0). Similarly, if xs is empty, return empty.

Wait, in Go, the function's parameter is []int, which can be nil. So, in the function, if xs is nil, we should treat it as an empty input and return an empty slice.

So, perhaps the first thing to do is check if xs is nil. If it is, return an empty slice. Or, perhaps, just proceed as normal because if xs is nil, iterating over it would cause a panic. So we need to handle the nil case first.

Wait, no. In Go, if you have a nil slice, you can't iterate over it because it's nil. So in the function, the first thing is to check if xs is nil. If it is, return an empty slice. Otherwise, proceed.

Wait, but in the examples, when the input is empty, the output is an empty slice. So perhaps the function can be written as:

if xs == nil {
    return []int{}
}

But wait, in Go, if you have an empty slice, like xs := []int{}, then len(xs) is 0, and xs is not nil. So the function can proceed as:

if len(xs) == 0 {
    return []int{}
}

But wait, the problem says that for an empty or nil input, return an empty, non-nil slice. So, if xs is nil, return []int{} (which is non-nil, length 0). If xs is empty (len 0), same.

So perhaps the first step is to check if xs is nil. If it is, return an empty slice. Otherwise, proceed.

Alternatively, perhaps the code can handle both cases by initializing the result as an empty slice and then processing each element.

So, the code outline is:

Create a map to track seen elements.

Create a result slice.

Iterate over each element in xs:

   if element is not in the map:

       add to result

       add to map

So, in code:

seen := make(map[int]bool)
result := []int{}

for _, num := range xs {
    if !seen[num] {
        result = append(result, num)
        seen[num] = true
    }
}

return result

But wait, what about the case when xs is nil? Because in Go, if you loop over a nil slice, it will panic. So the function needs to handle that.

So, the code should first check if xs is nil. If it is, return an empty slice. Otherwise, proceed.

So, putting it all together:

func Unique(xs []int) []int {
    if xs == nil {
        return []int{}
    }
    seen := make(map[int]bool)
    result := []int{}
    for _, num := range xs {
        if !seen[num] {
            seen[num] = true
            result = append(result, num)
        }
    }
    return result
}

Wait, but what about when xs is empty? Like xs is []int{}? Then the loop doesn't run, and result is empty, which is correct.

Testing the examples:

Example 1: Unique([]int{3, 1, 3, 2, 1}) should return [3,1,2].

Let's see:

Loop:

3 is not seen: add to result, seen[3] = true.

1 is not seen: add, seen[1] = true.

3 is seen: skip.

2 is not seen: add, seen[2] = true.

1 is seen: skip.

Result is [3,1,2]. Correct.

Example 2: [1,2,3] returns same.

Each is added once.

Example 3: [5,5,5] returns [5].

Yes.

Example 4: empty input returns empty.

Yes.

What about nil input? The function returns empty slice, which is correct.

Another test case: what if the input is nil? Like Unique(nil) should return []int{}.

Yes.

So this code should handle all cases.

Wait, but in Go, when you pass a nil slice to the function, the first condition xs == nil is true, so it returns an empty slice.

Yes.

So the code should be correct.