# Go Leetcode: Two Pointer

###### tags: `leetcode` `go`

## Container With Most Water
### #1

func maxArea(height []int) int {
    i, j := 0, len(height) - 1
    max := 0
    for i < j {
        // main logic
        cur_prod := min(height[i], height[j]) * (j-i)
        if max < cur_prod { max = cur_prod }
        if height[i] < height[j] {
            // left move
            for i < j {
                i++
                if height[i] > height[i-1] { break }
            }
        } else {
            // right move
            for i < j {
                j--
                if height[j] > height[j+1] { break }
            }
        }
    }
    return max
}

func min(i, j int) int {
    if i < j {
        return i
    } else {
        return j
    }
}

### #2 refactor

func maxArea(height []int) int {
    i, j := 0, len(height) - 1
    max := 0
    for i < j {
        // main logic
        if height[i] < height[j] {
            max = maxx(max, height[i] * (j-i))
            // left move
            for i < j {
                i++
                if height[i] > height[i-1] { break }
            }
        } else {
            max = maxx(max, height[j] * (j-i))
            // right move
            for i < j {
                j--
                if height[j] > height[j+1] { break }
            }
        }
    }
    return max
}

func maxx(i, j int) int {
    if i < j {
        return j
    } else {
        return i
    }
}

### #3 extremely fast

func init() {
	in := bufio.NewScanner(os.Stdin)
	in.Buffer(nil, math.MaxInt32)
	_out, _ := os.Create("user.out") // create file. must be "user.out" for leetcode
	out := bufio.NewWriter(_out)
	for in.Scan() {
		s := in.Bytes()
		n := bytes.Count(s, []byte{','}) + 1 // count amount of ","
		ans, l, r, i, j, readL, readR := 0, 0, n-1, 0, len(s)-1, true, true
		var x, y int
		for l < r {
			if readL {
				readL = false
				i++
				x = int(s[i] & 15)
				i++
				for s[i]&15 < 10 {
					x = x*10 + int(s[i]&15)
					i++
				}
			}
			if readR {
				readR = false
				for j -= 2; s[j]&15 < 10; j-- {
				}
				k := j + 1 // j is indes of ","
				y = int(s[k] & 15)
				k++
				for s[k]&15 < 10 {
					y = y*10 + int(s[k]&15)
					k++
				}
			}
			ans = max(ans, min(x, y)*(r-l))
			if x < y {
				l++
				readL = true
			} else {
				r--
				readR = true
			}
		}
		fmt.Fprintln(out, ans)
	}
	out.Flush()
	os.Exit(0)
}

func maxArea([]int) (_ int) { return }

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

## Two Sum II - Input Array Is Sorted
### #1 hash map

func twoSum(numbers []int, target int) []int {    
    m := make(map[int]int) // number: index
    for i, n := range numbers {
        pair := target - n
        if m[pair] > 0 {
            return []int{m[pair], i+1}
        }
        m[n] = i+1
    }
    return []int{}
}

### #2 two pointers

func twoSum(numbers []int, target int) []int {    
    l, r := 0, len(numbers)-1
    for {
        sum := numbers[l] + numbers[r]
        if sum > target {
            r--
        } else if sum < target {
            l++
        } else {
            return []int{l+1, r+1} // sum = target
        }
        // should not happen
        if l >= r {
            return []int{}
        }
    }
}

## Three Sum

### #1 fail

func threeSum(nums []int) [][]int {
    // time: O(n)
    m := make(map[int][]int)
    for i, n := range nums {
        m[n] = append(m[n], i)
    }
    fmt.Println(m)
    // time: <= O(n2)
    res := [][]int{}
    for l := 0; l < len(nums); l++ {
        first := nums[l]
        for r := l+1; r < len(nums); r++ {
            second := num[r]
            third := 0-first-second
            
        }
    }

    return res
}

func sliceEqual(a, b []int) bool {
    if len(a) != len(b) { return false }
    sort.Ints(a)
    sort.Ints(b)
    for i:= 0; i<len(a); i++ {
        if a[i] != b[i] {
            return false
        }
    }
    return true
}

### #2 close but fail

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    res := [][]int{}
    for i, a := range nums {
        l, r := i+1, len(nums)-1
        for l< r {
            b, c := nums[l], nums[r]
            sum := a + b + c
            if sum > 0 {
                r--
            } else if sum < 0 {
                l++
            } else {
                res = append(res, []int{a, b, c})
                l++
            }
        }
    }
    return res
}

input: [-1,0,1,2,-1,-4]
output: [[-1,-1,2],[-1,0,1],[-1,0,1]]
expected: [[-1,-1,2],[-1,0,1]]

### #3 success

func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    res := [][]int{}
    for i, a := range nums {
        // ignore same value
        if i > 0 && a == nums[i-1] {
            continue
        }
        
        l, r := i+1, len(nums)-1
        for l< r {
            b, c := nums[l], nums[r]
            sum := a + b + c
            if sum > 0 {
                r--
            } else if sum < 0 {
                l++
            } else {
                res = append(res, []int{a, b, c})
                l++
                // if next num equals to prev
                for nums[l] == nums[l-1] && l < r { l++ }
            }
        }
    }
    return res
}

### Note
- need to ignore duplicated numbers
- is an extension of [Two Sum II](/#)
- Time:
- sorting: O(nlogn)
- finding: O(n2)

## Valid Palindrome

### #3 best

func isPalindrome(s string) bool {
    l, r := 0, len(s)-1
    res := true
    for l<r {
        for !check(s[l]) {
            l++
            if l >= r { break }
        }
        for !check(s[r]) {
            r--
            if l >= r { break }
        }
        if l >= r { break }
        
        if !equals(s[l], s[r]) { return false }
        l++
        r--
    }
    return res
}

func check(char byte) bool {
    if 'a' <= char && char <= 'z' {
        return true
    } else if '0' <= char && char <= '9' {
        return true
    } else if 'A' <= char && char <= 'Z' {
        return true
    }
    return false
}

func equals(a, b byte) bool {
    if a == b { return true }
    if 'A' <= a && a <= 'Z' {
        return a+32 == b // 'a' - 'A' = 32
    } else if 'A' <= b && b <= 'Z' {
        return a == b+32
    }
    return false
}

### Resources
[用Go刷LeetCode和OJ](https://zhangjk98.xyz/go-oj/)