sudopower

lc_3542

LC: 3542: Minimum Operations to Convert All Elements to Zero

Link to problem

Solution 1 – Timeout O(n2)

func minOperations(nums []int) int {
    var ops int

    for idx,curDigit := range nums {
        if curDigit==0{
            continue
        }

        
        nums[idx]=0
        ops++
        for i:=idx+1;i<len(nums);i++{
            
            if nums[i]==curDigit{
                nums[i]=0
                continue
            }

            if nums[i]==0 {                
                break
            }

            if nums[i] < curDigit{
                break
            }
        }        
        
    }

    return ops
}

Solution 2 – Using stack

type Stack struct {
	data []int
}

func (stk *Stack) push(data int) {
	stk.data = append(stk.data, data)
}

func (stk *Stack) pop() int {
	if len(stk.data) == 0 {
		return -1
	}
	top := stk.data[len(stk.data)-1]
	stk.data = stk.data[:len(stk.data)-1]
	return top
}

func (stk *Stack) peek() int {
	if len(stk.data) == 0 {
		return -1
	}
	return stk.data[len(stk.data)-1]
}

func (stk *Stack) len() int {
    return len(stk.data)
}

func minOperations(nums []int) int {
    var ops int    
    var stack Stack
    for _,curDigit := range nums {
        for curDigit<stack.peek(){
            ops++
            stack.pop()
        }
        if  curDigit>0 && stack.peek()!=curDigit {
            stack.push(curDigit)
        }        
    }    

    return ops+stack.len()
}

Possible optimizations:

  1. Try making peek faster by storing top as part of stack ?
  2. No stack approach ?
    • Single loop array manipulation .. to be checked