### First Unique Character in a String - Leet Code Solution

Problem Statement Given a string, find the first non-repeating character in it…

September 01, 2020

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

**Example**

```
Input: [2,2,1]
Output: 1
Input: [4,1,2,1,2]
Output: 4
```

We can take help of `HashMap`

where we can save numbers and their counts.

- In first iteration, just fill this
`HashMap`

- Iterate over this
`HashMap`

, and find the number whose count is not 2

```
public int singleNumber_extraMemory(int[] nums) {
int l = nums.length;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i=0; i<l; i++) {
Integer count = map.get(nums[i]);
if (count == null) {
count = 1;
}
else {
count ++;
}
map.put(nums[i], count);
}
for (Integer key : map.keySet()) {
if (map.get(key) != 2) {
return key;
}
}
return -1;
}
```

The complexity of above code is `O(n)`

If we can sort the numbers, then we will have all pair of numbers adjascent to each other.

Then, we can check pair of numbers where they are not equal.

```
public int singleNumber_sort(int[] nums) {
int l = nums.length;
Arrays.sort(nums);
int i=0;
while (i<l-1) {
if (nums[i] != nums[i+1]) {
return nums[i];
}
i += 2;
}
//check for last element
if (l % 2 == 1) {
return nums[l-1];
}
return -1;
}
```

Since we are sorting, and iterating over array once. The complexity is `O(nlogn)`

Assuming our array has all pairs. i.e. we don’t have a single number. Then, following is true:

`2 (sum of unique numbers) = (sum of all numbers)`

Now, if we know one of the number is missing in pairs. Following must be true:

`2 (sum of unique numbers) - (sum of all numbers) = Missing Number`

Lets take a look at example:

```
#input [2, 2, 1]
2 * (2 + 1) - (2 + 2 + 1)
= 6 - 5
= 1
Result = 1
#Another example
# input [4,1,2,1,2]
2 * (4 + 1 + 2) - (4+1+2+1+2)
= 14 - 10
= 4
Result = 4
```

```
public int singleNumber(int[] nums) {
int l = nums.length;
Set<Integer> set = new HashSet<>();
int sum = 0;
int uniqueElementSum = 0;
for (int i=0; i<l; i++) {
if (!set.contains(nums[i])) {
set.add(nums[i]);
uniqueElementSum += nums[i];
}
//all sum
sum += nums[i];
}
return 2 * uniqueElementSum - sum;
}
```

We require a `HashSet`

just to check for unique elements.

The complexity is `O(n)`

Problem Statement Given a string, find the first non-repeating character in it…

Problem Statement Roman numerals are represented by seven different symbols: I…

Problem Statement Determine whether an integer is a palindrome. An integer is a…

Problem Statement The string “PAYPALISHIRING” is written in a zigzag pattern on…

Max Priority Queue is a data structure which manage a list of keys(values). And…

Counting sort runs on relatively smaller set of input. Counting sort calculates…

Introduction In this post we will see following: How to schedule a job on cron…

Introduction There are some cases, where I need another git repository while…

Introduction In this post, we will see how to fetch multiple credentials and…

Introduction I have an automation script, that I want to run on different…

Introduction I had to write a CICD system for one of our project. I had to…

Introduction Java log4j has many ways to initialize and append the desired…