// return true if there are dup items in array
// pre: nums[1,2,3,1]
// post: true
public boolean containsDuplicate(int[] nums) {
    // corner case: if nums.length <= 1, return false 
    if (nums.length <= 1) return false;

    Map<Integer, Boolean> map = new HashMap<>();
    // single linear scan left -> right, build hashMap as we go
    for (int num : nums) {
        // if map.containsKey(nums[i]) == true, then dup found so return true
        if (map.containsKey(num)) return true;

        map.put(num, true);
    }

    // return false
    return false;
}

class Solution:
    # return true if nums[] contains duplicate
    # pre: nums[1,2,3,1]
    # post: true
    def containsDuplicate(self, nums: List[int]) -> bool:
        # corner case: nums is empty or size 1, return false
        if len(nums) <= 1:
            return False;

        # step1: single linear scan left -> right, build hashMap as we go
        map = {}

        for num in nums:
            # step 2: if map.containsKey(nums[i]) == true, then dup found so return true
            if num in map:
                return True;

            map[num] = True

        return False;

// return index of first char that is unique
// pre: s="leetcode"
// post: 0
public int firstUniqChar(String s) {
    // corner case: if s.length <=1, return 0
    if (s.length() == 1) return 0;

    Map<Integer, Integer> map = new HashMap<>();

    // need to scan all the chars and keep count of occurrence
    for (char c : s.toCharArray()) {
        if (!map.containsKey((int) c)) {
            map.put((int) c, 1);
        }
        else {
            map.put((int) c, map.get((int) c) + 1); // increment count
        }
    }

    // second pass: need to go through string again to return index 
    for (int i = 0; i < s.length(); i++) {
        if (map.get((int) s.charAt(i)) == 1) {
            return i;
        }
    }

    return -1;
}

class Solution:
    # return index of first unique char in array
    # pre: s = "leetcode"
    # post: 0
    def firstUniqChar(self, s: str) -> int:    
        map = {}

        # step1: single linear scan left -> right
        for char in s:
            if char in map:
                map[char] = map[char] + 1
            else:
                map[char] = 1

        # step 2: second pass, need to go through string again to return index 
        for i in range(0, len(s)):
            if map[s[i]] == 1:
                return i

        return -1

public int[] twoSum(int[] nums, int target) {
    // clarification: guaranteed to have a pair sums up to target
    int[] result = new int[2];

    // logic: single linear scan left-right - nums[0...i...N-1]
    Map<Integer, Integer> hashmap = new HashMap<>();
    // test case: [2,7,1], target=3
    for (int i = 0; i < nums.length; i++) {
        // if nums[i] is in hashMap or hashMap.contains(target - nums[i]), then found it, need to return indeces so return [i, hashMap.get(nums[i])]
        if (hashmap.containsKey(nums[i])) {
            result[0] = hashmap.get(nums[i]);
            result[1] = i;
            break;
        }

        // else, put target-nums[i] and i as key-value as Entry(diff, index)
        hashmap.put(target - nums[i], i);
    }

    return result;
}

class Solution:
    # return indeces of two items summing up to target
    # pre: nums[2,7,11,15],target=9
    # post: [0,1]
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        results = []
        map = {}

        # step1: linear scan array left -> right, and build map       
        for i in range(0, len(nums)):
            # step 2: check if (target - nums[i]) exists in hashmap, if so return two indices
            complement = target - nums[i]
            if complement in map:
                # return indeces
                results.append(map[complement])
                results.append(i)
            else:
                # step 3: else, add (nums[i], i) to hashmap
                map[nums[i]] = i

        return results;

// reverse chars in array in-place
// pre: chars[dog]
// post: chars[god]
public void reverseString(char[] s) {
    // input check: if empty, return s
    if (s.length == 0) return;

    // run front & end indeces toward the middle and swap
    int front = 0;
    int end = s.length - 1;
    // test1: char[d,o,g], front=0, end=2
    // test2: char[d,o], front=0, end=1
    while (front < end) {
        char tmp = s[front];
        s[front] = s[end];
        s[end] = tmp;

        front++;
        end--;

        // test1: char[g,o,d], front=1, end=1
        // test2: char[o,d], front=1, end=0
    }
}

class Solution:
    # reverse chars in string in place
    # pre: s="dog"
    # post: s="god"
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        def swap(s: List[str], front: int, end: int):
            tmp = s[front]
            s[front] = s[end]
            s[end] = tmp

        # step1: run front & end indeces toward the middle
        front = 0
        end = len(s) - 1

        # testcases: s="", s="a", s="ab", s="abc"
        while front < end:
            # step 2: swap array[front] and array[end]
            swap(s, front, end)

            # step 3: move indeces
            front += 1
            end -= 1

// move zeros to the end while maintaining non-zero item's order
// pre: nums[0,1,0,3,12]
// post: nums[1,3,12,0,0]
public void moveZeroes(int[] nums) {
    // corner case: if nums.length == 0, return it
    if (nums.length == 0) return;

    int nonZeroLast = 0;
    int runnerIndex = 0;
    // linear scan left -> right while runnerIndex < nums.length
    while (runnerIndex < nums.length) {
        // split array into two sections, non-zero and zero sections using two indeces

        // if nums[runnerIndex] != 0, then swap(nums[nonZeroLast], nums[runnerIndex])
        // test case: nums[0,1,0,3,12], nonZeroIndex=0, runner=0
        // test case: nums[0,1,0,3,12], nonZeroIndex=0, runner=1
        // test case: nums[1,0,0,3,12], nonZeroIndex=1, runner=2
        // test case: nums[1,0,0,3,12], nonZeroIndex=1, runner=3
        if (nums[runnerIndex] != 0) {
            swap(nums, nonZeroLast, runnerIndex);

            // advance nonZeroLast only when after swapped
            nonZeroLast++;
        }

        // always advance runnerIndex++
        // test case: nums[0,1,0,3,12], nonZeroIndex=0, runner=1
        // test case: nums[1,0,0,3,12], nonZeroIndex=1, runner=2
        // test case: nums[1,0,0,3,12], nonZeroIndex=1, runner=3
        // test case: nums[1,3,0,0,12], nonZeroIndex=2, runner=4
        runnerIndex++;
    }

    return;
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

class Solution:
    # move all zeros toward the end, while maintaining non-zero item order
    # pre: nums[0,1,0,3,12]
    # post: nums[1,3,12,0,0]
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        def swap(nums: List[int], i: int, j: int):
            tmp = nums[i]
            nums[i] = nums[j]
            nums[j] = tmp

        # step1: linear scan left -> right while runnerIndex < nums.length
        nonZeroLastIndex = 0
        runner = 0

        # testcases: nums[], nums[1], nums[1,3], nums[1,3,0], nums[0], nums[0,3], nums[1,0,3]
        while runner < len(nums):
            # step 2: split array into two sections, non-zero and zero sections using two indeces

            # step 3: if nums[runnerIndex] != 0, then swap(nums[nonZeroLast], nums[runnerIndex])
            if nums[runner] != 0:
                swap(nums, nonZeroLastIndex, runner)
                nonZeroLastIndex += 1

            runner += 1

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

// "remove val from array" (move them to end) and return length of non-val-array
// pre: nums[3,2,2,3], val=3
// post: 2, nums[2,2,3,3]
public int removeElement(int[] nums, int val) {
    // corner case: val might not exist

    // single linear scan left -> right
    int nonValLastIndex = 0;
    int runner = 0;

    // testcase1: nums[3,2,2,3], val=3, nonVal=0, runner=0
    // testcase1: nums[3,2,2,3], val=3, nonVal=0, runner=1
    // testcase1: nums[2,3,2,3], val=3, nonVal=1, runner=2
    // testcase1: nums[2,2,3,3], val=3, nonVal=2, runner=3

    // testcase2: nums[3,3], val=3, nonVal=0, runner=0
    // testcase2: nums[3,3], val=3, nonVal=0, runner=1

    // testcase3: nums[2,3], val=3, nonVal=0, runner=0
    // testcase3: nums[2,3], val=3, nonVal=1, runner=1
    while (runner < nums.length) {
        // split array into two sections: non-val vs val
        // if nums[runner] == val, then move on

        // if nums[runner] != val, swap(nums[nonValLastIndex], nums[runner] )
        if (nums[runner] != val) {
            swap(nums, nonValLastIndex, runner);
            nonValLastIndex++;
        }

        runner++;
    }

    // return nonValLastIndex
    return nonValLastIndex;
}

private void swap(int[] nums, int index1, int index2) {
    int tmp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = tmp;
}

class Solution:
    # return length of array section without value
    # pre: nums[3,2,2,3], val=3
    # post: 2 (nums[2,2,3,3])
    def removeElement(self, nums: List[int], val: int) -> int:
        def swap(nums: List[int], i: int, j: int):
            tmp = nums[i]
            nums[i] = nums[j]
            nums[j] = tmp

        # step1: linear scan left -> right while runnerIndex < nums.length
        nonValLastIndex = 0
        runner = 0

        # testcase: nums[3,2,2,3], val=0
        while runner < len(nums):
            # step 2: split array into two sections, non-val and val sections using two indeces

            # step 3: if nums[runnerIndex] != val, then swap(nums[nonValLastIndex], nums[runnerIndex])
            if nums[runner] != val:
                swap(nums, nonValLastIndex, runner)
                nonValLastIndex += 1

            runner += 1

        return nonValLastIndex;