// The function bellow twoSumA time complexity is O(n^2) because it runs two for loop on a Slice.

func twoSumA(nums []int, target int) []int {
  for indexI, valI := range nums {
    for indexJ, valJ := range nums {
      if valI + valJ == target && indexI != indexJ {
        return []int{indexI, indexJ}
      }
    }
  }
  return []int{}
}

// This function uses hash table to reduce O(n^2) complexity to O(n) and space complexity increased from O(1) to O(n)
// In this method

func twoSumB(nums []int, target int) []int {
  tmp := make(map[int]int)
  for index, val := range nums {
    complement := target - val
    if j, ok := tmp[complement]; ok {
      return []int{j, index}
    }
    tmp[val] = index
  }
  return []int{}
}

func isPalindromeA(x int) bool {
  if x < 0 {
    return false
  }
  tmpNum := x
  rev := int(0)
  for tmpNum > 0 {
    d := tmpNum % 10
    rev = rev * 10 + d
    tmpNum = tmpNum / 10
  }
  if rev == x {
    return true
  }
  return false
}

func romanToInt(s string) int {
    romanToIntSum := int(0)
    tmpString := string("")
    insideString := string("")
    mapString := map[string]int{
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000,
    "IX": 9,
    "IV": 4,
    "XC": 90,
    "XL": 40,
    "CM": 900,
    "CD": 400,
    }
    for i := 0; i < len(s); i++ {
    insideString = string(s[i])
    if tmpString != "" {
      if twoLetter, ok := mapString[tmpString + insideString]; ok {
        romanToIntSum = romanToIntSum + twoLetter
        tmpString = ""
        continue
      }
      if oneLetter, ok := mapString[tmpString]; ok {
        romanToIntSum = romanToIntSum + oneLetter
        tmpString = insideString
        continue
      }
      return 0
    }
    tmpString = insideString
  }
  if tmpString != "" {
        romanToIntSum = romanToIntSum + mapString[tmpString]
    }
    return romanToIntSum
}

func longestCommonPrefix(strs []string) string {
  if len(strs) == 0 {
    return ""
  }
  for i := 0; i < len(strs[0]); i++ {
    c := strs[0][i]
    for j := 1; j < len(strs); j++ {
      if i == len(strs[j]) || strs[j][i] != c {
        return strs[0][:i]
      }
    }
  }
  return strs[0]
}