Smallest String With Swaps

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string. You can swap the characters at any pair of indices in the given pairs any number of times. Return the lexicographically smallest string that s can be changed to after using the swaps. Example 1 Input: s = "dcab", pairs = [[0,3],[1,2]] Output: "bacd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[1] and s[2], s = "bacd" Example 2 Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]] Output: "abcd" Explaination: Swap s[0] and s[3], s = "bcad" Swap s[0] and s[2], s = "acbd" Swap s[1] and s[2], s = "abcd" Example 3 Input: s = "cba", pairs = [[0,1],[1,2]] Output: "abc" Explaination: Swap s[0] and s[1], s = "bca" Swap s[1] and s[2], s = "bac" Swap s[0] and s[1], s = "abc" Constraints 1 <= s.

by lek tin in "algorithm" access_time 3-min read

Number of Islands Ii

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

by lek tin in "algorithm" access_time 3-min read

Critical Routers

You are given an undirected connected graph. An articulation point (or cut vertex) is defined as a vertex which, when removed along with associated edges, makes the graph disconnected (or more precisely, increases the number of connected components in the graph). The task is to find all articulation points in the given graph. Input: The input to the function/method consists of three arguments: numNodes, an integer representing the number of nodes in the graph.

by lek tin in "algorithm" access_time 1-min read

Critical Connections

Given an underected connected graph with n nodes labeled 1..n. A bridge (cut edge) is defined as an edge which, when removed, makes the graph disconnected (or more precisely, increases the number of connected components in the graph). Equivalently, an edge is a bridge if and only if it is not contained in any cycle. The task is to find all bridges in the given graph. Output an empty list if there are no bridges.

by lek tin in "algorithm" access_time 3-min read

Largest Component Size by Common Factor

Given a non-empty array of unique positive integers A, consider the following graph: There are A.length nodes, labelled A[0] to A[A.length - 1]; There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1. Return the size of the largest connected component in the graph. Example 1 Input: [4,6,15,35] Output: 4 Example 2 Input: [20,50,9,63] Output: 2 Example 3 Input: [2,3,6,7,4,12,21,39] Output: 8 Note 1 <= A.

by lek tin in "algorithm" access_time 2-min read