1. [Graph] Word Ladder Graph
2. [Misc] Floyd’s Cycle Finding Algorithm
3. [Misc] Exactly K to Atmost(K)
4. [Misc] Finding Top-K

[Graph] Word Ladder Graph

Problem Statement: How to make edges for a Graph, in a list of words, where only one character is different? i.e., to add edges between the nodes (words), where only a single character is different.

• For each word, add it to the dictionary with keys having _ at every character location. Now, for each dictionary key, connect all values as edges in the graph.

Example: Given a list wordList, return a graph where the words which differs by a single letter are connected via direct edges [LC #127: Word Ladder]

d = defaultdict(list)
for word in wordList:
	for idx in range(len(word)):
	key = word[:idx]+'_'+word[idx+1:]
	d[key].append(word)
g = defaultdict(list)
for key in d.keys():
	total_items = len(d[key])
	for idx in range(total_items):
		word1 = d[key][idx]
		for jdx in range(idx+1, total_items):
		word2 = d[key][jdx]
		g[word1].append(word2)
		g[word2].append(word1)

[Misc] Floyd’s Cycle Finding Algorithm

In Linked List, a cycle can be detected by using two pointers, one fast (2x speed) and other slow. If the pointers meet, there is a cycle otherwise not.

How to detect the beginning point of cycle?

Let us consider the two pointers met at node h. There are F nodes out of the cycle and (a + b) nodes inside the cycle. Since, the two pointers met at h,

1. Set ptr_1 to the list head, and ptr_2 to the intersection node.
2. Traverse both pointers one point at a time, the meeting point is the cycle entrance.

Question: [Leetcode #142]

The next function of linked list can be emulated in arrays using nums[nums[i]]. In an n + 1 element array with elements ranging from 1to n, if there is an element in the array repeated multiple times, it can be detected using the same idea. [Leetcode #287]

[Misc] Exactly K to Atmost(K)

For some problems, it is better to convert exactly K solution to a difference of atmost(K) - atmost(K-1). For example, consider problem https://leetcode.com/problems/subarrays-with-k-different-integers/, finding the atleast K is easy. [Leetcode #992]

To-DO

[Misc] Finding Top-K

Find the top $k^{th}$ or top-$k$ elements. [Leetcode #347] [Leetcode #973]

Solution Approach :

• Sorting: Brute force approach is sorting and takes $O(NlogN)$ time
• Heaps: TC:O(NlogK), SC:O(N+K)
  • Step 1: Do heapify for $K$ items in the list. TC:$O(K)$
  • Step 2: Do push and pop operations in the heap according to the value. C:$O(NlogK)$
• QuickSelect: TC is $O(N)$ in average case, and $O(N^2)$ in worst case