Word ladder and maximum subarray in Java 2 questions in 3 chapters

  1. 01Shortest word transformations
  2. 02Maximum subarray sums
  3. 03Sources

Shortest word transformations

BFS over a word graph, using wildcard patterns to find one-letter neighbors.

  • 1.1 How do you find the length of the shortest word ladder? Hard 4 min

    I model this as BFS on an unweighted word graph. If the end word is not in the list I return zero. I bucket words under wildcard patterns like h*t, so one-letter neighbors share a pattern. Search starts at the begin word, visits each word once, and returns the word count when it reaches the end. That's roughly O(N L²). A follow-up is bidirectional BFS.

    Read the full answer

Maximum subarray sums

Kadane's one-pass algorithm, plus indices, divide and conquer, and the circular variant.

  • 2.1 How do you find the maximum sum of a contiguous subarray? Medium 5 min

    I use Kadane's algorithm: one pass that keeps the best sum ending here and the best sum so far, in linear time and constant space. At each number I either extend the previous run or start a new one here, then update the global best. Both values start at the first element, so an all-negative array returns the largest element. Follow-ups are the indices, divide and conquer, and the circular variant.

    Read the full answer

Sources