NUHMAN.com

🧩 Problem Statement

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

📘 Example

go

Input: nums = [1,2,3,1]
Output: true

Input: nums = [1,2,3,4]
Output: false

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

🧠 Approach

We can solve this easily using a hash set:

• Iterate through each number
• If it's already in the set, return true
• Otherwise, add it to the set
• If we finish the loop, return false

✅ Go Implementation

go

package main

import "fmt"

func containsDuplicate(nums []int) bool {
    seen := make(map[int]bool)

    for _, num := range nums {
        if seen[num] {
            return true
        }
        seen[num] = true
    }

    return false
}

📦 Example Usage

go

func main() {
    fmt.Println(containsDuplicate([]int{1, 2, 3, 1}))       // true
    fmt.Println(containsDuplicate([]int{1, 2, 3, 4}))       // false
    fmt.Println(containsDuplicate([]int{1,1,1,3,3,4,3,2}))  // true
}

⏱️ Time & Space Complexity

• Time: O(n) — iterate over the array once
• Space: O(n) — for storing seen elements in the hash set

Let me know if you’d like to continue with the next one (218. The Skyline Problem) or skip around!

You said:

please do the same for 218. The Skyline Problem

ChatGPT said:

Sure! Here's the breakdown and Go implementation for LeetCode 218: The Skyline Problem.

🔢 Problem Title: 218. The Skyline Problem

Tags: Heap, Divide and Conquer, Sorting, Sweep Line, Go

🧩 Problem Statement

A city's skyline is the outer contour of the silhouette of all the buildings in the city when viewed from a distance.

You are given a 2D array buildings where each building is represented by a triplet of integers [left, right, height]:

• left is the x-coordinate of the left edge of the building,
• right is the x-coordinate of the right edge of the building,
• height is the height of the building.

The skyline should be a list of key points in the form [x, height] that uniquely defines the outline of the city, ordered by their x-coordinate.

📘 Example

go

Input: buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

🧠 Approach

We can solve this problem using a sweep line algorithm combined with a max heap:

1. Create events for both the start and end of each building. Each event is either a start (left) or an end (right) of a building, represented as a pair of (x-coordinate, height, type) where type is 1 for start and -1 for end.
2. Sort all events by the x-coordinate. If two events have the same x-coordinate, sort by height.
3. Sweep through the events:

• For start events, add the building height to the heap.
• For end events, remove the building height from the heap.

1. Track the maximum height at each x-coordinate. Whenever the maximum height changes, it means a key point of the skyline has been reached.

✅ Go Implementation

go

package main

import (
	"container/heap"
	"fmt"
	"sort"
)

// Event structure for a building's start and end point
type Event struct {
	x      int
	height int
	typeOf int // 1 for start, -1 for end
}

// MaxHeap is a max-heap based on building height
type MaxHeap []int

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] } // reverse order for max-heap
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func getSkyline(buildings [][]int) [][]int {
	var events []Event

	// Create events for start and end of buildings
	for _, building := range buildings {
		events = append(events, Event{building[0], building[2], 1})  // start event
		events = append(events, Event{building[1], building[2], -1}) // end event
	}

	// Sort events: first by x-coordinate, then by type (start before end) and height (higher first)
	sort.Slice(events, func(i, j int) bool {
		if events[i].x == events[j].x {
			return events[i].typeOf > events[j].typeOf // start before end
		}
		return events[i].x < events[j].x
	})

	var result [][]int
	maxHeap := &MaxHeap{}
	heap.Init(maxHeap)
	heap.Push(maxHeap, 0) // Add a dummy height to make sure we start with a valid max height

	for _, event := range events {
		if event.typeOf == 1 {
			// Start of a building, add its height to the max heap
			heap.Push(maxHeap, event.height)
		} else {
			// End of a building, remove its height from the max heap
			// This is done lazily, the actual removal happens by checking the top of the heap
			// and popping the elements when needed.
			removeHeight(maxHeap, event.height)
		}

		// Get the current max height
		currHeight := (*maxHeap)[0]

		// If the height changes, add a key point to the result
		if len(result) == 0 || result[len(result)-1][1] != currHeight {
			result = append(result, []int{event.x, currHeight})
		}
	}

	return result
}

// Helper function to remove a height from the max heap
func removeHeight(h *MaxHeap, height int) {
	// We use lazy deletion by pushing the height and removing it later from the heap
	for i := 0; i < len(*h); i++ {
		if (*h)[i] == height {
			// Replace it with the last element
			(*h)[i] = (*h)[len(*h)-1]
			*h = (*h)[:len(*h)-1]
			heap.Init(h)
			return
		}
	}
}

func main() {
	buildings := [][]int{{2, 9, 10}, {3, 7, 15}, {5, 12, 12}, {15, 20, 10}, {19, 24, 8}}
	result := getSkyline(buildings)
	fmt.Println(result) // Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
}

📦 Example Usage

go

func main() {
    buildings := [][]int{{2, 9, 10}, {3, 7, 15}, {5, 12, 12}, {15, 20, 10}, {19, 24, 8}}
    result := getSkyline(buildings)
    fmt.Println(result) // Output: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
}

⏱️ Time & Space Complexity

• Time: O(n log n), where n is the number of events (2 times the number of buildings), because sorting the events takes O(n log n) time, and each heap operation (push and pop) takes O(log n).
• Space: O(n), for storing events and heap operations.