Two pointers

// Sorted input. Returns [lo, hi] indices, or null.
function twoSumSorted(nums, target) {
  let lo = 0;
  let hi = nums.length - 1;

  // `lo < hi`, not `<=`: an element may not pair with itself.
  while (lo < hi) {
    const sum = nums[lo] + nums[hi];
    if (sum === target) return [lo, hi];
    if (sum < target) lo++;   // nums[lo]'s best partner was too small
    else hi--;                // nums[hi]'s best partner was too large
  }
  return null;
}

console.log(twoSumSorted([2, 7, 11, 15, 19, 22], 26));  // [1,4] -> 7+19
console.log(twoSumSorted([2, 7, 11, 15], 100));         // null
console.log(twoSumSorted([3, 3], 6));                   // [0,1] -> duplicates are fine
console.log(twoSumSorted([3], 6));                      // null -> single element

# Sorted input. Returns [lo, hi] indices, or None.
def two_sum_sorted(nums, target):
    lo = 0
    hi = len(nums) - 1

    # `lo < hi`, not `<=`: an element may not pair with itself.
    while lo < hi:
        total = nums[lo] + nums[hi]
        if total == target:
            return [lo, hi]
        if total < target:
            lo += 1     # nums[lo]'s best partner was too small
        else:
            hi -= 1     # nums[hi]'s best partner was too large
    return None


print(two_sum_sorted([2, 7, 11, 15, 19, 22], 26))  # [1, 4] -> 7+19
print(two_sum_sorted([2, 7, 11, 15], 100))         # None
print(two_sum_sorted([3, 3], 6))                   # [0, 1] -> duplicates are fine
print(two_sum_sorted([3], 6))                      # None -> single element

[1, 4]
None
[0, 1]
None

// Remove duplicates from a sorted array, in place. Returns the new length.
function dedupeSorted(nums) {
  if (nums.length === 0) return 0;

  // INVARIANT: nums[0..write-1] holds the distinct values seen so far, in order.
  let write = 1;
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[write - 1]) {
      nums[write] = nums[read];
      write++;
    }
  }
  return write;
}

const a = [1, 1, 2, 2, 2, 3, 4, 4];
const n = dedupeSorted(a);
console.log(`length ${n}, prefix ${JSON.stringify(a.slice(0, n))}, full array ${JSON.stringify(a)}`);

import json


# Remove duplicates from a sorted list, in place. Returns the new length.
def dedupe_sorted(nums):
    if len(nums) == 0:
        return 0

    # INVARIANT: nums[0..write-1] holds the distinct values seen so far, in order.
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1
    return write


a = [1, 1, 2, 2, 2, 3, 4, 4]
n = dedupe_sorted(a)
# `separators=(",", ":")` makes json.dumps print like JSON.stringify; the
# default adds a space after every comma.
compact = lambda x: json.dumps(x, separators=(",", ":"))
print(f"length {n}, prefix {compact(a[:n])}, full array {compact(a)}")

length 4, prefix [1,2,3,4], full array [1,2,3,4,2,3,4,4]

// Build a list with a cycle, then locate its entrance.
function makeList(values, cycleStartIndex) {
  const nodes = values.map((v) => ({ v, next: null }));
  for (let i = 0; i < nodes.length - 1; i++) nodes[i].next = nodes[i + 1];
  if (cycleStartIndex >= 0) nodes[nodes.length - 1].next = nodes[cycleStartIndex];
  return nodes[0];
}

function cycleStart(head) {
  let slow = head;
  let fast = head;

  // Phase one: find a meeting point inside the cycle, if there is one.
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      // Phase two: mu = n*lambda - k, so head and meeting point are
      // equidistant from the entrance.
      let probe = head;
      while (probe !== slow) {
        probe = probe.next;
        slow = slow.next;
      }
      return probe.v;
    }
  }
  return null;
}

console.log(cycleStart(makeList([1, 2, 3, 4, 5, 6, 7], 2)));  // 3 -> entrance value
console.log(cycleStart(makeList([1, 2, 3], -1)));             // null -> no cycle
console.log(cycleStart(makeList([1], 0)));                    // 1 -> self-loop

# Build a list with a cycle, then locate its entrance.
class Node:
    def __init__(self, v):
        self.v = v
        self.next = None


def make_list(values, cycle_start_index):
    nodes = [Node(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if cycle_start_index >= 0:
        nodes[-1].next = nodes[cycle_start_index]
    return nodes[0]


def cycle_start(head):
    slow = head
    fast = head

    # Phase one: find a meeting point inside the cycle, if there is one.
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:            # `is` compares identity, like `===` on JS objects
            # Phase two: mu = n*lambda - k, so head and meeting point are
            # equidistant from the entrance.
            probe = head
            while probe is not slow:
                probe = probe.next
                slow = slow.next
            return probe.v
    return None


print(cycle_start(make_list([1, 2, 3, 4, 5, 6, 7], 2)))  # 3 -> entrance value
print(cycle_start(make_list([1, 2, 3], -1)))             # None -> no cycle
print(cycle_start(make_list([1], 0)))                    # 1 -> self-loop

3
None
1