Solving Leetcode Problems with Golang

Problem: Container With Most Water

Alec Garza

Published in

CodeX

4 min readJan 28, 2022

source: What is Golang and How to Install It | by Sayan Mondal | Level Up Coding (gitconnected.com)

Motivation

Recently, I decided that I wanted to prep for interviews, coding competitions, and learn a new programming language. To kill all of these birds with one stone, I decided to practice Leetcode problems daily with Golang. Solving algorithm problems in a language you aren’t familiar with forces you to think about the problem that actually needs to be solved, which helps you become a better developer. Of course, there are the initial hiccups with getting the correct syntax, but the most important thing is being able to solve problems regardless of tooling.

Soon after this journey began, I noticed that there isn’t nearly as much support for Leetcode problems in Golang as there is C++, Python, or Java. Given the history of those languages, its not surprising that a modern language like Go doesn’t have the same level of support. However, this article will be the first in a series of posts where I provide solutions to Leetcode problems in Golang.

DISCLAIMER: As mentioned before, I am still learning Go. If anyone has any recommendations to make my code more idiomatic, please provide in the comments.

Container With Most Water

Difficulty: Medium

Pass Rate: 53%

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Problem Breakdown

In short, they want you to treat the coordinates for the lines as sides of a rectangle and find the combination of sides that return the largest area of the formed rectangle.

The problem states that you may not slant the container. In the image, you can see that the answer involves two sides where one is height 8, and the other is height 7. This is important to note, because we must make sure that the sides of the rectangle are balanced, so when dealing with two uneven sides, we will perform the computation for rectangle area with whichever side is the smaller of the two.

The difference between the indexes j and i will provide us the length of the rectangle. So our computation for the rectangle’s area will look like:

area = rectLength * rectHeight

rectLength = j-i

rectHeight= height[i]

Naïve Approach

The naive/brute force approach involves utilizing a nested for loop to iterate through each possible. After breaking down and understanding the problem, it is always good to implement the naive approach and then make it more efficient. The idea is to never shoot straight for the most efficient approach first. You must understand the problem, and how to get that problem solved first. Efficiency is a luxury of mastery.

Here is the brute force solution in Golang, which has a suboptimal O(n²) runtime due to the utilization of nested for loops.

func maxArea(height []int) int {
    var maxArea int = 0
    var size int = len(height)
    
    for i := 0; i < size; i++ {
        currentArea := 0
        for j := 0; j < size; j++ {
            segmentLength := j-i
            var segmentHeight int = height[i]
            
            if(segmentHeight >= height[j]) {
                segmentHeight = height[j]
            }
            
            currentArea = segmentLength*segmentHeight
            if(currentArea > maxArea) {
                maxArea = currentArea
            }
        }
    }
    
    return maxArea
}

This code will provide the correct answer, but fail the test cases due to exceeding the minimum acceptable time limit. Now, we optimize.

Optimized Solution

Optimizing this solution involves noticing a subtlety in the problem. If we were to start with i at the beginning of the array and j at the end, we could move the pointers inward and calculate the areas of the rectangles that way. To move the pointers inward, we would increment i and decrement j.

How does this help us? Because since the length will be continuously getting smaller, the only way that the area could get larger is if the height increases.

If two pointers are involved, the brute force algorithm is O(n²), and the problem involves us searching for a combination of sub elements that meet a given criteria, then we are 9/10 times going to use a sliding window approach to the optimized solution.

A sliding window approach saves us many small computational steps but most importantly allows us to refactor our code into an O(n) solution.

Here is the optimized solution:

func maxArea(height []int) int {
    var maxArea int = 0
    var i int = 0
    var j int = len(height)-1
    var result int = 0
    
    for i < j {        
        if(height[i] <= height[j]) {
            result = height[i] * (j-i)
            i++
        } else {
            result = height[j] * (j-i)
            j--
        }
                
        if(result > maxArea) {
            maxArea = result
        }
    }
    return maxArea
}