Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 393
Good morning! Here's your coding interview problem for today.

This problem was asked by Airbnb.

Given an array of integers, return the largest range, inclusive, of integers that are all included in the array.

For example, given the array `[9, 6, 1, 3, 8, 10, 12, 11]`, return `(8, 12)` since `8, 9, 10, 11, and 12` are all in the array.

Pull request:
Day393
Resolves #789.

Patch:
diff --git a/README.md b/README.md
index 0d47e64..b70ef7e 100644
--- a/README.md
+++ b/README.md
@@ -385,4 +385,5 @@ problems from
 * [Day 390](https://github.com/vaskoz/dailycodingproblem-go/issues/783)
 * [Day 391](https://github.com/vaskoz/dailycodingproblem-go/issues/785)
 * [Day 392](https://github.com/vaskoz/dailycodingproblem-go/issues/787)
+* [Day 393](https://github.com/vaskoz/dailycodingproblem-go/issues/789)
 
diff --git a/day393/problem.go b/day393/problem.go
new file mode 100644
index 0000000..458c52d
--- /dev/null
+++ b/day393/problem.go
@@ -0,0 +1,84 @@
+package day393
+
+import "sort"
+
+// LargestRangeBrute returns the largest range of integers
+// using brute force.
+// Runtime is O(N*K) where K is the length of the longest range.
+// Effectively, this is O(N^2).
+// Converts the input into a hash set.
+func LargestRangeBrute(nums []int) (int, int) {
+	if n := len(nums); n == 0 {
+		return 0, 0
+	} else if n == 1 {
+		return nums[0], nums[0]
+	}
+
+	set := make(map[int]struct{}, len(nums))
+
+	for _, num := range nums {
+		set[num] = struct{}{}
+	}
+
+	var longest, sAns, eAns int
+
+	for start := range set {
+		count := 1
+		ptr := start + 1
+
+		for _, found := set[ptr]; found; _, found = set[ptr] {
+			count++
+			ptr++
+		}
+
+		if count > longest || (count == longest && start < sAns) {
+			longest = count
+			sAns = start
+			eAns = ptr - 1
+		}
+	}
+
+	return sAns, eAns
+}
+
+// LargestRangeSort returns the largest range of integers
+// using slightly better than brute-force.
+// Runtime is O(N log N).
+// Performs a copy to avoid mutating the input.
+func LargestRangeSort(nums []int) (int, int) {
+	if n := len(nums); n == 0 {
+		return 0, 0
+	} else if n == 1 {
+		return nums[0], nums[0]
+	}
+
+	copied := append([]int{}, nums...)
+
+	sort.Ints(copied)
+
+	var longest, sAns, eAns, start, end, count int
+
+	count = 1
+	start = copied[0]
+
+	for i := 1; i < len(copied); i++ {
+		if copied[i] == copied[i-1]+1 {
+			count++
+		} else {
+			end = copied[i-1]
+			if end-start > longest {
+				sAns, eAns = start, end
+				longest = count
+			}
+			start = copied[i]
+			count = 1
+		}
+	}
+
+	end = copied[len(copied)-1]
+	if end-start > longest {
+		sAns, eAns = start, end
+	}
+
+	return sAns, eAns
+}


Test patch:
diff --git a/day393/problem_test.go b/day393/problem_test.go
new file mode 100644
index 0000000..e2741ef
--- /dev/null
+++ b/day393/problem_test.go
@@ -0,0 +1,51 @@
+package day393
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	nums       []int
+	start, end int
+}{
+	{[]int{9, 6, 1, 3, 8, 10, 12, 11}, 8, 12},
+	{[]int{}, 0, 0},
+	{nil, 0, 0},
+	{[]int{12}, 12, 12},
+	{[]int{9, 1, 3, 8, 10, 12, 11, 2, 4, 5}, 1, 5},
+}
+
+func TestLargestRangeBrute(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if s, e := LargestRangeBrute(tc.nums); s != tc.start || e != tc.end {
+			t.Errorf("Expected (%v,%v), got (%v,%v)", tc.start, tc.end, s, e)
+		}
+	}
+}
+
+func BenchmarkLargestRangeBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LargestRangeBrute(tc.nums)
+		}
+	}
+}
+
+func TestLargestRangeSort(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if s, e := LargestRangeSort(tc.nums); s != tc.start || e != tc.end {
+			t.Errorf("Expected (%v,%v), got (%v,%v)", tc.start, tc.end, s, e)
+		}
+	}
+}
+
+func BenchmarkLargestRangeSort(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LargestRangeSort(tc.nums)
+		}
+	}
+}