Skip to content

Instantly share code, notes, and snippets.

@manjeettahkur

manjeettahkur/leetcodeQuestions.go

Created January 25, 2026 02:49
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save manjeettahkur/210455e1564e71872946b75885f9cb64 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save manjeettahkur/210455e1564e71872946b75885f9cb64 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
leetcodeQuestions.go
package main
import (
"container/heap"
"fmt"
"math"
"slices"
"sort"
"strings"
)
func main() {
// base := []int{1, 2, 3, 4}
//fmt.Println(bounceFill(base, 5))
// input := "bbbbb"
// x := [][]int{{2, 6}, {8, 10}, {1, 3}}
// sortIntervals(x)
// fmt.Println(mergeInterval(x))
// fmt.Println(maxProfit([]int{7, 1, 5, 3, 6, 4}))
// fmt.Println(twoSum([]int{3, 2, 4}, 6))
// fmt.Println(groupAnagrams([]string{"eat", "tea", "tan", "ate", "nat", "bat"}))
// fmt.Println(longestCommonPrefix([]string{"flow", "flower", "flight"}))
// fmt.Println(findPoisonedDuration([]int{1, 2}, 2))
// fmt.Println(sensor([]int{2,7}, 6))
// fmt.Println(tMAx([]int{1, 2, -2147483648}))
// fmt.Println(strStr("hello", "ll"))
// fmt.Println(maxProfitX([]int{7,6,4,0,3,1}))
// fmt.Println(myAtoi(" "))
// fmt.Println(threeSum([]int{0, 0, 0}))
// fmt.Println(firstMissingPositive([]int{1}))
// fmt.Println(longestSubarray([]int{8, 2, 4, 7}, 4))
// fmt.Println(maxSum([]int{2, 1, 5, 1, 3, 2}, 3))
// fmt.Println(longestKSubstring("ABAB", 2))
// fmt.Println(maxInNWindows([]int{1, 3, -1, -3, 5, 3, 6, 7}, 3))
fmt.Println(generateParenthesis(3))
}
// Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
// Output: [3,3,5,5,6,7]
// [1,3,4,5,1]
// [-4, -1, -1, 0, 1, 2]
// [[-1,-1,2], [-1,0,1]]
// func triplet([]int)[][]int{
// }
func generateParenthesis(n int) []string {
var result []string
var backtrack func(current string, open, close int)
backtrack = func(current string, open, close int) {
// Base case: complete string
if open == n && close == n {
result = append(result, current)
return
}
// Choice 1: add ( if allowed
if open < n {
backtrack(current+"(", open+1, close)
fmt.Println("XXX:", current)
}
// Choice 2: add ) if allowed
if close < open {
backtrack(current+")", open, close+1)
fmt.Println("YYY:", current)
}
}
backtrack("", 0, 0)
return result
}
// func generateParenthesis(n int) []string {
// if n == 0 {
// return []string{""}
// }
// var res []string
// for k := range n {
// fmt.Printf("\n N:-{%d} ::K:: - [%d] N-1-K - [%d]\n",n, k, n-k-1)
// left := generateParenthesis(k)
// right := generateParenthesis(n-1-k)
// for _, a := range left {
// for _, b := range right {
// res = append(res, "("+a+")"+b)
// }
// }
// }
// return res
// }
func maxInNWindows(input []int, k int) []int {
l := 0
var maxDeque MonoDecDeque
if len(input) == 0 {
return []int{}
}
output := []int{}
for r, num := range input {
maxDeque.Push(num)
if r-l+1 > k {
maxDeque.Pop(input[l])
l++
}
if r-l+1 == k {
max := maxDeque.Max()
output = append(output, max)
}
}
return output
}
func getMaxCount(counts map[rune]int) int {
maxVal := 0
for _, count := range counts {
if count > maxVal {
maxVal = count
}
}
return maxVal
}
func longestKSubstring(s string, k int) int {
l := 0
freq := make(map[rune]int)
maxSubString := 0
for r, c := range s {
freq[c]++
maxFreq := getMaxCount(freq)
for (r-l+1)-maxFreq > k {
freq[rune(s[l])]--
if freq[rune(s[l])] == 0 {
delete(freq, rune(s[l]))
}
l++
}
maxSubString = max(maxSubString, r-l+1)
}
return maxSubString
}
func longest(s string) int {
l := 0
freq := make(map[rune]int)
maxLength := 0
for r, c := range s {
freq[c]++
for freq[c] > 1 {
leftChar := rune(s[l])
freq[leftChar]--
l++
}
maxLength = max(maxLength, r-l+1)
}
return maxLength
}
func maxSum(arr []int, k int) int {
l := 0
maxTotalSum := 0
currSum := 0
for r := range arr {
currSum += arr[r]
if r-l+1 > k {
currSum -= arr[l]
l++
}
if r-l+1 == k {
maxTotalSum = max(maxTotalSum, currSum)
}
}
return maxTotalSum
}
type MonoIncDeque struct {
data []int
}
func (m *MonoIncDeque) Push(x int) {
for len(m.data) > 0 && m.data[len(m.data)-1] > x {
m.data = m.data[:len(m.data)-1]
}
m.data = append(m.data, x)
}
func (m *MonoIncDeque) Pop(x int) {
if len(m.data) > 0 && m.data[0] == x {
m.data = m.data[1:]
}
}
func (m MonoIncDeque) Min() int {
return m.data[0]
}
type MonoDecDeque struct {
data []int
}
func (m *MonoDecDeque) Push(x int) {
for len(m.data) > 0 && m.data[len(m.data)-1] < x {
m.data = m.data[:len(m.data)-1]
}
m.data = append(m.data, x)
}
func (m *MonoDecDeque) Pop(x int) {
if len(m.data) > 0 && m.data[0] == x {
m.data = m.data[1:]
}
}
func (m MonoDecDeque) Max() int {
return m.data[0]
}
func longestSubarray(nums []int, limit int) int {
l := 0
var maxDeque MonoDecDeque
var miDeque MonoIncDeque
longest := 0
for r := range nums {
maxDeque.Push(nums[r])
miDeque.Push(nums[r])
// IF max - min <= limit then expand the window
for maxDeque.Max()-miDeque.Min() > limit {
miDeque.Pop(nums[l])
maxDeque.Pop(nums[l])
l++
}
longest = max(longest, r-l+1)
}
return longest
}
func firstMissingPositive(nums []int) int {
i := 0
n := len(nums)
for i < n {
if (nums[i] >= 1 && nums[i] <= n) && (nums[i] != nums[nums[i]-1]) {
nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
} else {
i++
}
}
for i, num := range nums {
if num != i+1 {
return i + 1
}
}
return n + 1
}
func longestPalindrome(s string) string {
if len(s) == 0 {
return ""
}
start := 0
maxLen := 0
expandAroundCentre := func(s string, left, right int) int {
for left >= 0 && right < len(s)-1 && s[left] == s[right] {
left--
right++
}
return right - left - 1
}
for i := 0; i < len(s); i++ {
len1 := expandAroundCentre(s, i, i)
len2 := expandAroundCentre(s, i, i+1)
currLen := max(len1, len2)
if currLen > maxLen {
maxLen = currLen
start = i - (currLen-1)/2
}
}
return s[start : start+maxLen]
}
func bounceFill(base []int, n int) []int {
if len(base) == 0 || n <= 0 {
return []int{}
}
out := make([]int, 0, n)
idx := 0
dir := 1 // +1 = forward, -1 = backward
for len(out) < n {
out = append(out, base[idx])
// Move index
idx += dir
// Bounce at edges
if idx == len(base)-1 || idx == 0 {
// Stay one extra step at the edge
if len(out) < n {
out = append(out, base[idx])
}
dir *= -1 // reverse direction
}
}
return out[:n] // trim if we overshoot by 1
}
func threeSum(nums []int) [][]int {
// Sort the input
slices.Sort(nums)
n := len(nums)
output := [][]int{}
for i := range nums {
if i > 0 && nums[i] == nums[i-1] {
continue
}
j := i + 1
k := n - 1
for j < k {
total := nums[i] + nums[j] + nums[k]
if total == 0 {
output = append(output, []int{nums[i], nums[j], nums[k]})
j++
k--
for nums[j] == nums[j-1] && j < k {
j++
}
for nums[k] == nums[k+1] && j < k {
k--
}
} else if total < 0 {
j++
} else if total > 0 {
k--
}
}
}
return output
}
func myAtoi(s string) int {
const INT_MAX = 1<<31 - 1
const INT_MIN = -1 << 31
sign := 1
n := len(s)
i := 0
for (i < n) && (s[i] == ' ') {
i++
}
if (i < n) && (s[i] == '-' || s[i] == '+') {
if s[i] == '-' {
sign = -1
}
i++
}
output := 0
for i < n {
ch := s[i]
if ch < '0' || ch > '9' {
break
}
digit := int(ch - '0')
if sign == 1 {
if output > INT_MAX/10 || (output == INT_MAX/10 && digit > 7) {
return INT_MAX
}
} else {
if output > INT_MAX/10 || (output == INT_MAX/10 && digit > 8) {
return INT_MIN
}
}
output = output*10 + digit
i++
}
return output * sign
}
func strStr(haystack string, needle string) int {
n, m := len(haystack), len(needle)
if m == 0 {
return 0
}
fmt.Println(n - m)
for i := 0; i <= n-m; i++ {
if haystack[i:i+m] == needle {
return i
}
}
return -1
}
func maxProfitX(prices []int) int {
if len(prices) < 2 {
return 0
}
maxProfit := 0
minPrice := prices[0]
for _, price := range prices[1:] {
if price < minPrice {
minPrice = price
} else {
profit := price - minPrice
maxProfit += profit
minPrice = price
}
}
return maxProfit
}
type MaxHeap []int
func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
old := *h
x := old[len(old)-1]
*h = old[:len(old)-1]
return x
}
func tMAx(nums []int) int {
// 1. Initialize Heap
h := &MaxHeap{}
heap.Init(h)
// 2. Insert all numbers
for _, num := range nums {
heap.Push(h, num)
}
// 3. Logic to find 3rd distinct max
var maxVal int
distinctCount := 0
// Use a very small number or a flag to track previous value
// Since input can be anything, let's use a pointer just for the 'previous' tracking
// to handle the "nil" state of the first iteration.
var prev *int
for h.Len() > 0 {
top := heap.Pop(h).(int)
// If this is the first item, or different from the previous item
if prev == nil || top != *prev {
distinctCount++
// Capture the absolute maximum (the first distinct item popped)
if distinctCount == 1 {
maxVal = top
}
// If we found the 3rd distinct one, return it immediately
if distinctCount == 3 {
return top
}
// Update prev.
// Note: Creating a new variable 'val' ensures 'prev' points
// to a unique memory location, preventing loop variable reuse issues.
val := top
prev = &val
}
}
// If the loop finished and we didn't find 3 distinct values,
// the rule is to return the Maximum value.
return maxVal
}
func thirdMax(nums []int) int {
first, second, third := math.MinInt32, math.MinInt32, math.MinInt32
for _, num := range nums {
if num == first || num == second || num == third {
continue
}
if num > first {
third = second
second = first
first = num
} else if num > second {
third = second
second = num
} else if num > third {
third = num
}
}
if third == math.MinInt32 {
return first
}
return third
}
func sensor(events []int, duration int) int {
total := 0
for i := range events {
total += duration
if i < len(events)-1 && events[i+1]-events[i] < duration {
total -= duration - (events[i+1] - events[i])
}
}
return total
}
//
func longestCommonPrefixTest() {
testes := []struct {
input []string
expectedOutput string
description string
}{
{
input: []string{"flow", "flower", "flight"},
expectedOutput: "fl",
description: "common prefix exists",
},
}
for _, tc := range testes {
got := longestCommonPrefix(tc.input)
if got != tc.expectedOutput {
fmt.Println(fmt.Errorf("expected %q, got %q", tc.expectedOutput, got))
}
}
}
// func findPoisonedDuration(timeSeries []int, duration int) int {
// totalPoisoned := 0
// for i := 0; i < len(timeSeries)-1; i++ {
// gap := timeSeries[i+1] - timeSeries[i]
// if gap >= duration {
// totalPoisoned += duration
// } else {
// totalPoisoned += gap
// }
// }
// totalPoisoned += duration
// return totalPoisoned
// }
func findPoisonedDuration(timeSeries []int, duration int) int {
poisonedDuration := 0
l := len(timeSeries) - 1
for i := range timeSeries {
poisonedDuration += duration
if i < l && (timeSeries[i+1]-timeSeries[i]) < duration {
poisonedDuration -= duration - (timeSeries[i+1] - timeSeries[i])
}
}
return poisonedDuration
}
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
for i := 0; i < len(strs[0]); i++ {
for j := 1; j < len(strs); j++ {
if i >= len(strs[j]) || strs[j][i] != strs[0][i] {
return strs[0][:i]
}
}
}
return strs[0]
}
func groupAnagrams(anagrams []string) [][]string {
anagramsMap := make(map[string][]string)
for _, anagram := range anagrams {
x := strings.Split(anagram, "")
sort.Strings(x)
t := strings.Join(x, "")
if _, ok := anagramsMap[t]; ok {
anagramsMap[t] = append(anagramsMap[t], anagram)
} else {
anagramsMap[t] = append(anagramsMap[t], anagram)
}
}
fmt.Printf("#+v", anagramsMap)
return nil
}
func twoSum(nums []int, target int) []int {
seen := make(map[int]int)
for i, num := range nums {
if index, ok := seen[target-num]; ok {
return []int{index, i}
}
seen[num] = i
}
return []int{-1, -1}
}
func maxProfit(prices []int) int {
if len(prices) < 2 {
return 0
}
minPrice := prices[0]
highProfit := 0
currentProfit := 0
for _, price := range prices {
if price < minPrice {
minPrice = price
}
currentProfit = price - minPrice
highProfit = max(currentProfit, highProfit)
}
return highProfit
}
func mergeInterval(intervals [][]int) [][]int {
output := [][]int{}
if len(intervals) == 0 {
return [][]int{}
}
output = append(output, intervals[0])
for i := 1; i < len(intervals); i++ {
lastIndex := len(output) - 1
lastMergeInterval := output[lastIndex]
if intervals[i][0] <= lastMergeInterval[1] {
output[len(output)-1][1] = max(intervals[i][1], lastMergeInterval[1])
} else {
output = append(output, intervals[i])
}
}
return output
}
func sortIntervals(intervals [][]int) [][]int {
slices.SortStableFunc(intervals, func(a, b []int) int {
if a[0] < b[0] {
return -1
} else if a[0] > b[0] {
return 1
}
return 0
})
return intervals
}
func longestPrefixSum(input string) int {
left := 0
maxLen, currentLen := 0, 0
seen := make(map[rune]int)
for right, char := range input {
seen[char]++
for seen[char] > 1 {
seen[rune(input[left])]--
left++
}
currentLen = right - left + 1
maxLen = max(maxLen, currentLen)
}
return maxLen
}
// package main
// import "fmt"
// func main() {
// x := []int{1, 2, 3, 4}
// xLen := len(x)
// answer := make([]int, xLen)
// answer[0] = 1
// for i := 1; i < xLen; i++ {
// answer[i] = x[i-1] * answer[i-1]
// }
// rightProduct := 1
// for i := xLen - 1; i >= 0; i-- {
// answer[i] = answer[i] * rightProduct
// rightProduct *= x[i]
// }
// fmt.Println(answer)
// }
// package main
// import "fmt"
// func main() {
// heights := []int{1, 8, 6, 2, 5, 4, 8, 3, 7}
// maxWater := 0
// left := 0
// right := len(heights) - 1
// for left < right {
// width := right - left
// height := min(heights[left], heights[right])
// temp := width * height
// maxWater = max(temp, maxWater)
// if heights[left] < heights[right] {
// left++
// } else {
// right--
// }
// }
// fmt.Println(maxWater)
// }
// package main
// import (
// "fmt"
// "log"
// "net/http"
// _ "net/http/pprof"
// "github.com/gorilla/websocket"
// )
// func ws(w http.ResponseWriter, r *http.Request) {
// fmt.Println("I'm called")
// upgrader := websocket.Upgrader{}
// conn, err := upgrader.Upgrade(w, r, nil)
// if err != nil {
// return
// }
// for {
// _, msg, err := conn.ReadMessage()
// if err != nil {
// conn.Close()
// return
// }
// log.Printf("msg: %s", string(msg))
// }
// }
// func main() {
// http.HandleFunc("/", ws)
// go func() {
// if err := http.ListenAndServe("localhost:6060", nil); err != nil {
// log.Fatalf("Pprof failed: %v", err)
// }
// }()
// fmt.Printf("Server will be running on port 8000")
// if err := http.ListenAndServe(":8000", nil); err != nil {
// log.Fatal(err)
// }
// }
// // func main() {
// // var rLimit syscall.Rlimit
// // if err := syscall.Getrlimit(syscall.RLIMIT_NOFILE, &rLimit); err != nil {
// // panic(err)
// // }
// // rLimit.Cur = rLimit.Max
// // if err := syscall.Setrlimit(syscall.RLIMIT_NOFILE, &rLimit); err != nil {
// // panic(err)
// // }
// // go func () {
// // if err := http.ListenAndServe("localhost:6060", nil); err != nil {
// // log.Fatalf("pprof failed: %v", err)
// // }
// // }()
// // var err error
// // epoller, err = MKEpoll
// // fmt.Println("Hello World")
// // }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment