Big-O & Complexity

def contains_duplicate_quadratic(nums: list[int]) -> bool:
    """O(n²) time, O(1) space: compare every pair of positions."""
    for i in range(len(nums)):
        # Start j after i so each pair is checked once and never against itself.
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False


def contains_duplicate_linear(nums: list[int]) -> bool:
    """O(n) time, O(n) space: remember every value in a hash set."""
    seen: set[int] = set()
    for num in nums:
        if num in seen:  # O(1) on average, instead of a scan.
            return True
        seen.add(num)
    return False


if __name__ == "__main__":
    # Both versions agree on every input: true, false, true, false.
    for nums in [[1, 2, 3, 1], [1, 2, 3, 4], [1, 1, 1, 3, 3, 4, 3, 2, 4, 2], [7]]:
        print(contains_duplicate_quadratic(nums), contains_duplicate_linear(nums))

// O(n²) time, O(1) space: compare every pair of positions.
export function containsDuplicateQuadratic(nums: number[]): boolean {
  for (let i = 0; i < nums.length; i++) {
    // Start j after i so each pair is checked once and never against itself.
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] === nums[j]) return true;
    }
  }
  return false;
}

// O(n) time, O(n) space: remember every value in a hash set.
export function containsDuplicateLinear(nums: number[]): boolean {
  const seen = new Set<number>();
  for (const num of nums) {
    if (seen.has(num)) return true; // O(1) on average, instead of a scan.
    seen.add(num);
  }
  return false;
}

// Both versions agree on every input: true, false, true, false.
for (const nums of [[1, 2, 3, 1], [1, 2, 3, 4], [1, 1, 1, 3, 3, 4, 3, 2, 4, 2], [7]]) {
  console.log(containsDuplicateQuadratic(nums), containsDuplicateLinear(nums));
}

package main

import "fmt"

// containsDuplicateQuadratic takes O(n²) time and O(1) space: it compares
// every pair of positions.
func containsDuplicateQuadratic(nums []int) bool {
	for i := 0; i < len(nums); i++ {
		// Start j after i so each pair is checked once and never against itself.
		for j := i + 1; j < len(nums); j++ {
			if nums[i] == nums[j] {
				return true
			}
		}
	}
	return false
}

// containsDuplicateLinear takes O(n) time and O(n) space: it remembers every
// value in a hash set.
func containsDuplicateLinear(nums []int) bool {
	seen := map[int]bool{}
	for _, num := range nums {
		if seen[num] { // O(1) on average, instead of a scan.
			return true
		}
		seen[num] = true
	}
	return false
}

func main() {
	// Both versions agree on every input: true, false, true, false.
	for _, nums := range [][]int{{1, 2, 3, 1}, {1, 2, 3, 4}, {1, 1, 1, 3, 3, 4, 3, 2, 4, 2}, {7}} {
		fmt.Println(containsDuplicateQuadratic(nums), containsDuplicateLinear(nums))
	}
}

using System;
using System.Collections.Generic;

public class Solution
{
    // O(n²) time, O(1) space: compare every pair of positions.
    public static bool ContainsDuplicateQuadratic(int[] nums)
    {
        for (int i = 0; i < nums.Length; i++)
        {
            // Start j after i so each pair is checked once and never against itself.
            for (int j = i + 1; j < nums.Length; j++)
            {
                if (nums[i] == nums[j]) return true;
            }
        }
        return false;
    }

    // O(n) time, O(n) space: remember every value in a hash set.
    public static bool ContainsDuplicateLinear(int[] nums)
    {
        var seen = new HashSet<int>();
        foreach (int num in nums)
        {
            if (seen.Contains(num)) return true; // O(1) on average, instead of a scan.
            seen.Add(num);
        }
        return false;
    }

    public static void Main()
    {
        // Both versions agree on every input: true, false, true, false.
        int[][] inputs = { new[] { 1, 2, 3, 1 }, new[] { 1, 2, 3, 4 }, new[] { 1, 1, 1, 3, 3, 4, 3, 2, 4, 2 }, new[] { 7 } };
        foreach (int[] nums in inputs)
        {
            Console.WriteLine(ContainsDuplicateQuadratic(nums) + " " + ContainsDuplicateLinear(nums));
        }
    }
}

import java.util.HashSet;
import java.util.Set;

public class Solution {
    // O(n²) time, O(1) space: compare every pair of positions.
    static boolean containsDuplicateQuadratic(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            // Start j after i so each pair is checked once and never against itself.
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) return true;
            }
        }
        return false;
    }

    // O(n) time, O(n) space: remember every value in a hash set.
    static boolean containsDuplicateLinear(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        for (int num : nums) {
            if (seen.contains(num)) return true; // O(1) on average, instead of a scan.
            seen.add(num);
        }
        return false;
    }

    public static void main(String[] args) {
        // Both versions agree on every input: true, false, true, false.
        int[][] inputs = {{1, 2, 3, 1}, {1, 2, 3, 4}, {1, 1, 1, 3, 3, 4, 3, 2, 4, 2}, {7}};
        for (int[] nums : inputs) {
            System.out.println(containsDuplicateQuadratic(nums) + " " + containsDuplicateLinear(nums));
        }
    }
}

def missing_number(nums: list[int]) -> int:
    """The one number from 0 to n missing from `nums`, which holds n distinct
    numbers from that range."""
    n = len(nums)
    # 0 + 1 + ... + n by formula, so no loop is needed for the full total.
    missing = n * (n + 1) // 2
    # Subtract every number that is present. Only the missing one is left.
    for num in nums:
        missing -= num
    return missing


if __name__ == "__main__":
    print(missing_number([3, 0, 1]))  # 2
    print(missing_number([0, 1]))  # 2
    print(missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]))  # 8
    print(missing_number([1]))  # 0

// The one number from 0 to n missing from nums, which holds n distinct
// numbers from that range.
export function missingNumber(nums: number[]): number {
  const n = nums.length;
  // 0 + 1 + ... + n by formula, so no loop is needed for the full total.
  let missing = (n * (n + 1)) / 2;
  // Subtract every number that is present. Only the missing one is left.
  for (const num of nums) missing -= num;
  return missing;
}

console.log(missingNumber([3, 0, 1])); // 2
console.log(missingNumber([0, 1])); // 2
console.log(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1])); // 8
console.log(missingNumber([1])); // 0

package main

import "fmt"

// missingNumber returns the one number from 0 to n missing from nums, which
// holds n distinct numbers from that range.
func missingNumber(nums []int) int {
	n := len(nums)
	// 0 + 1 + ... + n by formula, so no loop is needed for the full total.
	missing := n * (n + 1) / 2
	// Subtract every number that is present. Only the missing one is left.
	for _, num := range nums {
		missing -= num
	}
	return missing
}

func main() {
	fmt.Println(missingNumber([]int{3, 0, 1}))                   // 2
	fmt.Println(missingNumber([]int{0, 1}))                      // 2
	fmt.Println(missingNumber([]int{9, 6, 4, 2, 3, 5, 7, 0, 1})) // 8
	fmt.Println(missingNumber([]int{1}))                         // 0
}

using System;

public class Solution
{
    // The one number from 0 to n missing from nums, which holds n distinct
    // numbers from that range.
    public static int MissingNumber(int[] nums)
    {
        int n = nums.Length;
        // 0 + 1 + ... + n by formula, so no loop is needed for the full total.
        int missing = n * (n + 1) / 2;
        // Subtract every number that is present. Only the missing one is left.
        foreach (int num in nums) missing -= num;
        return missing;
    }

    public static void Main()
    {
        Console.WriteLine(MissingNumber(new[] { 3, 0, 1 })); // 2
        Console.WriteLine(MissingNumber(new[] { 0, 1 })); // 2
        Console.WriteLine(MissingNumber(new[] { 9, 6, 4, 2, 3, 5, 7, 0, 1 })); // 8
        Console.WriteLine(MissingNumber(new[] { 1 })); // 0
    }
}

public class Solution {
    // The one number from 0 to n missing from nums, which holds n distinct
    // numbers from that range.
    static int missingNumber(int[] nums) {
        int n = nums.length;
        // 0 + 1 + ... + n by formula, so no loop is needed for the full total.
        int missing = n * (n + 1) / 2;
        // Subtract every number that is present. Only the missing one is left.
        for (int num : nums) missing -= num;
        return missing;
    }

    public static void main(String[] args) {
        System.out.println(missingNumber(new int[] {3, 0, 1})); // 2
        System.out.println(missingNumber(new int[] {0, 1})); // 2
        System.out.println(missingNumber(new int[] {9, 6, 4, 2, 3, 5, 7, 0, 1})); // 8
        System.out.println(missingNumber(new int[] {1})); // 0
    }
}