union-find | brain

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3666 - Minimum Operations to Equalize Binary String

LeetCode Problem 3666 Difficulty: 🔴 Hard Topics: Math, String, Breadth-First Search, Union-Find, Ordered Set Solution Problem Understanding The problem asks us to transform a binary string s consisting of characters '0' and '1' into a string where all characters are '1' . The allowed operation is flipping exactly k different indices in one move, turning '0' to '1' and '1' to '0' . The goal is to find the minimum...

Practice › LeetCode › LeetCode 39xx ›

LeetCode 3910 - Count Connected Subgraphs with Even Node Sum

LeetCode Problem 3910 Difficulty: 🔴 Hard Topics: Array, Bit Manipulation, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Enumeration Solution Correctness The solution does address the correct exercise and correctly identifies that the task is to generalize Algorithm S by handling the case when subtraction is performed without knowing which operand is larger. It correctly uses the standard TAOCP idea: if a final borrow remains, then the computed digit string represents...

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3887 - Incremental Even-Weighted Cycle Queries

LeetCode Problem 3887 Difficulty: 🔴 Hard Topics: Union-Find, Graph Theory Solution Problem Understanding This problem describes a dynamic process of building an undirected graph with weighted edges where the weights are binary, either 0 or 1. You start with n isolated nodes labeled from 0 to n-1 . You are given a list of potential edges with weights, and you must add each edge in the given order only if...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3613 - Minimize Maximum Component Cost

LeetCode Problem 3613 Difficulty: 🟡 Medium Topics: Binary Search, Union-Find, Graph Theory, Sorting Solution Problem Understanding The problem asks us to minimize the maximum cost among components in a connected undirected graph after removing edges. Each edge has a weight, and the cost of a connected component is the largest weight of any edge in that component. You can remove edges freely, but the graph must end up with at...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3608 - Minimum Time for K Connected Components

LeetCode Problem 3608 Difficulty: 🟡 Medium Topics: Binary Search, Union-Find, Graph Theory, Sorting Solution LeetCode 3608 - Minimum Time for K Connected Components Problem Understanding We are given an undirected graph with n vertices and a list of edges. Each edge has a removal time timei . The graph evolves over time. At time t , every edge whose removal time satisfies timei <= t has already been removed. All...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3600 - Maximize Spanning Tree Stability with Upgrades

LeetCode Problem 3600 Difficulty: 🔴 Hard Topics: Binary Search, Greedy, Union-Find, Graph Theory, Minimum Spanning Tree Solution Problem Understanding This problem asks us to determine the maximum possible stability of a spanning tree built from a weighted, undirected graph with certain constraints. Each edge in the graph has a strength and a mandatory flag . A mandatory edge ( musti == 1 ) must appear in the spanning tree, and...

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3873 - Maximum Points Activated with One Addition

LeetCode Problem 3873 Difficulty: 🔴 Hard Topics: Array, Hash Table, Union-Find Solution Problem Understanding The problem is asking us to simulate a chain reaction of activations on a set of 2D points. Each point is defined by its (x, y) coordinates and all points are distinct. When a point is activated, any point sharing the same x coordinate or y coordinate becomes activated as well. This activation propagates recursively: newly...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3710 - Maximum Partition Factor

LeetCode Problem 3710 Difficulty: 🔴 Hard Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem asks us to split a set of n points in a 2D Cartesian plane into exactly two non-empty groups, such that the minimum Manhattan distance among all pairs of points within each group (the partition factor) is maximized. The Manhattan distance between points [xi, yi] and [xj, yj]...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3695 - Maximize Alternating Sum Using Swaps

LeetCode Problem 3695 Difficulty: 🔴 Hard Topics: Array, Greedy, Union-Find, Sorting Solution LeetCode 3695 - Maximize Alternating Sum Using Swaps Problem Understanding We are given an array nums and a list of allowed swap operations. The alternating sum of an array is defined as: $$nums[0] - nums[1] + nums[2] - nums[3] + \cdots$$ Elements at even indices contribute positively, while elements at odd indices contribute negatively. The important detail is...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3619 - Count Islands With Total Value Divisible by K

LeetCode Problem 3619 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Problem Understanding The problem is asking us to count islands in a 2D grid where the sum of the values in each island is divisible by a given integer k . An island is defined as a group of positive integers that are 4-directionally connected, meaning we can move horizontally or vertically between adjacent positive...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3607 - Power Grid Maintenance

LeetCode Problem 3607 Difficulty: 🟡 Medium Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Heap (Priority Queue), Ordered Set Solution Problem Understanding The problem gives an undirected graph of c power stations labeled from 1 to c , connected by bidirectional cables. These connections define connected components, which are referred to as power grids. Importantly, these grids are static, meaning connectivity does not change even if stations...

Practice › LeetCode › LeetCode 35xx ›

LeetCode 3532 - Path Existence Queries in a Graph I

LeetCode Problem 3532 Difficulty: 🟡 Medium Topics: Array, Hash Table, Binary Search, Union-Find, Graph Theory Solution Path Existence Queries in a Graph I Problem Understanding This problem defines an undirected graph implicitly through a sorted array nums . Each index in nums represents a graph node. Two nodes i and j are connected by an edge whenever: $$|nums[i] - nums[j]| \le maxDiff$$ We are then given many connectivity queries. For...

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3493 - Properties Graph

LeetCode Problem 3493 Difficulty: 🟡 Medium Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem asks us to model a 2D array of integers, called properties , as an undirected graph. Each row of the array corresponds to a node in the graph. Two nodes are connected if the number of distinct integers they share is at least k . Our goal is...

Practice › LeetCode › LeetCode 31xx ›

LeetCode 3108 - Minimum Cost Walk in Weighted Graph

LeetCode Problem 3108 Difficulty: 🔴 Hard Topics: Array, Bit Manipulation, Union-Find, Graph Theory Solution Problem Understanding This problem gives us an undirected weighted graph with n vertices and up to 10^5 edges. Each edge connects two vertices and has an integer weight. For every query [s, t] , we must determine the minimum possible cost of any walk from node s to node t . The key detail is the...

Practice › LeetCode › LeetCode 25xx ›

LeetCode 2573 - Find the String with LCP

LeetCode Problem 2573 Difficulty: 🔴 Hard Topics: Array, String, Dynamic Programming, Greedy, Union-Find, Matrix Solution Problem Understanding The problem gives us an n x n matrix called lcp , where: lcp[i][j] represents the length of the longest common prefix between: the suffix starting at index i the suffix starting at index j If the unknown string is word , then: suffix i is word[i:] suffix j is word[j:] The task...

Practice › LeetCode › LeetCode 26xx ›

LeetCode 2658 - Maximum Number of Fish in a Grid

LeetCode Problem 2658 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Problem Understanding The problem provides a 2D grid representing a map of land and water cells. Each cell can either be land (value 0 ) or water containing a positive number of fish. The goal is to determine the maximum number of fish a fisher can collect by starting from any water cell and moving...

Practice › LeetCode › LeetCode 28xx ›

LeetCode 2852 - Sum of Remoteness of All Cells

LeetCode Problem 2852 Difficulty: 🟡 Medium Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution LeetCode 2852 - Sum of Remoteness of All Cells Problem Understanding We are given an n × n grid where each cell is either: A positive integer, representing a valid cell with that value. -1 , representing a blocked cell. Movement is allowed only between non-blocked cells that share an edge, meaning up,...

Practice › LeetCode › LeetCode 23xx ›

LeetCode 2382 - Maximum Segment Sum After Removals

LeetCode Problem 2382 Difficulty: 🔴 Hard Topics: Array, Union-Find, Prefix Sum, Ordered Set Solution Problem Understanding The problem gives us two arrays, nums and removeQueries , both of length n . The nums array contains positive integers. Initially, all elements are present, forming one contiguous segment. Then, elements are removed one by one according to the order defined in removeQueries . After each removal, the array becomes split into one...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2492 - Minimum Score of a Path Between Two Cities

LeetCode Problem 2492 Difficulty: 🟡 Medium Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem asks us to find the minimum possible score of a path between city 1 and city n in a graph defined by n cities and roads . Each road connects two cities bidirectionally and has an associated distance. The score of a path is defined as the minimum distance among all...

Practice › LeetCode › LeetCode 27xx ›

LeetCode 2709 - Greatest Common Divisor Traversal

LeetCode Problem 2709 Difficulty: 🔴 Hard Topics: Array, Math, Union-Find, Number Theory Solution Understood. I will provide the complete, detailed reference guide for LeetCode 2702 - Minimum Operations to Make Numbers Non-positive , following your formatting rules exactly. Problem Understanding The problem provides a 0-indexed integer array nums and two integers x and y . You are allowed to perform the following operation any number of times: choose an index...

Practice › LeetCode › LeetCode 23xx ›

LeetCode 2334 - Subarray With Elements Greater Than Varying Threshold

LeetCode Problem 2334 Difficulty: 🔴 Hard Topics: Array, Stack, Union-Find, Monotonic Stack Solution Problem Understanding This problem asks us to find a contiguous subarray whose elements are all sufficiently large relative to the subarray length. More specifically, for a subarray of length k , every element inside that subarray must satisfy: $$\text{element} > \frac{\text{threshold}}{k}$$ We are allowed to return the size k of any valid subarray. If no such subarray...

Practice › LeetCode › LeetCode 21xx ›

LeetCode 2157 - Groups of Strings

LeetCode Problem 2157 Difficulty: 🔴 Hard Topics: Array, Hash Table, String, Bit Manipulation, Union-Find Solution Problem Understanding The problem asks us to group a list of unique lowercase strings based on a special notion of connectivity. Each string can be represented as a set of letters , and two strings are connected if one can be transformed into the other with exactly one operation : adding a letter, removing a...

Practice › LeetCode › LeetCode 33xx ›

LeetCode 3378 - Count Connected Components in LCM Graph

LeetCode Problem 3378 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Union-Find, Number Theory Solution Problem Understanding We are given an array nums , where each element represents the value assigned to a node in a graph. The graph contains exactly n nodes, one node for each array element. Two nodes are connected by an undirected edge if the least common multiple of their values is less than or equal...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2424 - Longest Uploaded Prefix

LeetCode Problem 2424 Difficulty: 🟡 Medium Topics: Hash Table, Binary Search, Union-Find, Design, Binary Indexed Tree, Segment Tree, Heap (Priority Queue), Ordered Set Solution Problem Understanding The problem asks us to design a data structure that tracks uploaded videos and continuously reports the length of the longest uploaded prefix. A prefix of uploaded videos means that every video from 1 through i has already been uploaded. The goal is to...

Practice › LeetCode › LeetCode 25xx ›

LeetCode 2503 - Maximum Number of Points From Grid Queries

LeetCode Problem 2503 Difficulty: 🔴 Hard Topics: Array, Two Pointers, Breadth-First Search, Union-Find, Sorting, Heap (Priority Queue), Matrix Solution Problem Understanding The problem asks us to calculate the maximum number of points that can be collected in a grid for a series of queries. The grid is represented by an m x n matrix of integers, where each cell has a value. For each query value q , we start...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1998 - GCD Sort of an Array

LeetCode Problem 1998 Difficulty: 🔴 Hard Topics: Array, Math, Union-Find, Sorting, Number Theory Solution Problem Understanding The problem asks whether it is possible to sort an integer array nums into non-decreasing order using a very specific type of swap. You can swap any two elements nums[i] and nums[j] if and only if their greatest common divisor (GCD) is greater than 1. The input is an array of integers ranging from...

Practice › LeetCode › LeetCode 26xx ›

LeetCode 2612 - Minimum Reverse Operations

LeetCode Problem 2612 Difficulty: 🔴 Hard Topics: Array, Hash Table, Breadth-First Search, Union-Find, Ordered Set Solution This will be a very large, multi-thousand-word technical guide because of the required depth, full proofs, worked examples, Python and Go implementations, detailed walkthroughs, complexity reasoning, and exhaustive tests. To ensure quality and avoid truncation, I will split it cleanly into sections across messages. Part 1: Problem Understanding, Approaches, Algorithm Walkthrough, and Python Solution...

Practice › LeetCode › LeetCode 26xx ›

LeetCode 2685 - Count the Number of Complete Components

LeetCode Problem 2685 Difficulty: 🟡 Medium Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding This problem asks us to count how many connected components in an undirected graph are complete graphs . We are given an integer n , representing the number of vertices labeled from 0 to n - 1 , and a list of undirected edges. Each edge [a, b] means there is a bidirectional...

Practice › LeetCode › LeetCode 23xx ›

LeetCode 2371 - Minimize Maximum Value in a Grid

LeetCode Problem 2371 Difficulty: 🔴 Hard Topics: Array, Union-Find, Graph Theory, Topological Sort, Sorting, Matrix Solution Problem Understanding The problem presents a matrix grid of size m x n with distinct positive integers . The goal is to transform this matrix so that every element is replaced with another positive integer while maintaining the relative order in each row and column . This means that if an element was larger...

Practice › LeetCode › LeetCode 29xx ›

LeetCode 2948 - Make Lexicographically Smallest Array by Swapping Elements

LeetCode Problem 2948 Difficulty: 🟡 Medium Topics: Array, Union-Find, Sorting Solution Problem Understanding The problem asks us to transform a given array of positive integers nums into its lexicographically smallest form by performing a specific swap operation any number of times. The operation allows swapping any two elements nums[i] and nums[j] only if the absolute difference between them is at most limit . The lexicographically smallest array is one where,...

Practice › LeetCode › LeetCode 33xx ›

LeetCode 3383 - Minimum Runes to Add to Cast Spell

LeetCode Problem 3383 Difficulty: 🔴 Hard Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Topological Sort Solution Problem Understanding We are given a directed graph with n focus points, numbered from 0 to n - 1 . Some focus points already contain magic crystals. These are the starting sources of magic energy. Directed runes represent one-way magic flow between focus points. If there is a rune from u to...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1971 - Find if Path Exists in Graph

LeetCode Problem 1971 Difficulty: 🟢 Easy Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem asks us to determine whether a path exists between two nodes in an undirected graph. The graph is defined by n vertices labeled from 0 to n - 1 and a list of edges, where each edge connects two distinct vertices. The key points are that the graph is bi-directional ,...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1905 - Count Sub Islands

LeetCode Problem 1905 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Problem Understanding The problem presents two m x n binary matrices, grid1 and grid2 , representing maps of land ( 1 ) and water ( 0 ). Each matrix may contain multiple islands, where an island is defined as a connected group of 1 s that are adjacent vertically or horizontally . The task is...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1970 - Last Day Where You Can Still Cross

LeetCode Problem 1970 Difficulty: 🔴 Hard Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Problem Understanding This problem asks us to find the last day we can cross a grid from the top row to the bottom row, walking only on land. The grid is initially all land ( 0 ), and each day, specific cells are flooded with water ( 1 ) according to the cells...

Practice › LeetCode › LeetCode 27xx ›

LeetCode 2782 - Number of Unique Categories

LeetCode Problem 2782 Difficulty: 🟡 Medium Topics: Union-Find, Interactive, Counting Solution Problem Understanding This problem asks us to determine how many distinct categories exist among n elements. The elements are labeled from 0 to n - 1 , but we are not given the category values directly. Instead, we interact with the hidden categorization through the provided API: haveSameCategory(a, b) This function tells us whether two elements belong to the...

Practice › LeetCode › LeetCode 23xx ›

LeetCode 2307 - Check for Contradictions in Equations

LeetCode Problem 2307 Difficulty: 🔴 Hard Topics: Array, Depth-First Search, Union-Find, Graph Theory Solution Problem Understanding This problem gives us a collection of equations of the form: $$A_i / B_i = value_i$$ Each variable is represented as a string, and each equation defines a multiplicative relationship between two variables. The task is to determine whether all equations can simultaneously be true. If at least one equation conflicts with the others,...

Practice › LeetCode › LeetCode 26xx ›

LeetCode 2617 - Minimum Number of Visited Cells in a Grid

LeetCode Problem 2617 Difficulty: 🔴 Hard Topics: Array, Dynamic Programming, Stack, Breadth-First Search, Union-Find, Heap (Priority Queue), Matrix, Monotonic Stack Solution Problem Understanding The problem asks us to determine the minimum number of cells we need to visit in order to reach the bottom-right corner of a given m x n grid. Each cell (i, j) contains a number grid[i][j] representing the maximum number of steps we can move right...

Practice › LeetCode › LeetCode 28xx ›

LeetCode 2812 - Find the Safest Path in a Grid

LeetCode Problem 2812 Difficulty: 🟡 Medium Topics: Array, Binary Search, Breadth-First Search, Union-Find, Heap (Priority Queue), Matrix Solution LeetCode 2812 - Find the Safest Path in a Grid Problem Understanding This problem asks us to find a path from the top-left corner (0,0) to the bottom-right corner (n-1,n-1) that maximizes its safeness factor . The grid contains thieves, represented by cells with value 1 , and empty cells, represented by...

Practice › LeetCode › LeetCode 23xx ›

LeetCode 2316 - Count Unreachable Pairs of Nodes in an Undirected Graph

LeetCode Problem 2316 Difficulty: 🟡 Medium Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem asks us to find the number of pairs of nodes in an undirected graph that cannot reach each other via any path. You are given an integer n representing the total number of nodes labeled from 0 to n - 1 and a list of edges representing connections between nodes. Each...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2421 - Number of Good Paths

LeetCode Problem 2421 Difficulty: 🔴 Hard Topics: Array, Hash Table, Tree, Union-Find, Graph Theory, Sorting Solution Problem Understanding The problem is asking us to count the number of good paths in a tree. A tree is a connected acyclic graph with n nodes and n - 1 edges. Each node has an integer value assigned by the array vals . A good path is defined as a simple path (no...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2493 - Divide Nodes Into the Maximum Number of Groups

LeetCode Problem 2493 Difficulty: 🔴 Hard Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding We are given an undirected graph with n nodes and a list of edges. The graph may contain multiple disconnected components. Our task is to divide all nodes into ordered groups numbered from 1 to m . The key constraint is based on graph edges. If two nodes are connected by an edge,...

Practice › LeetCode › LeetCode 23xx ›

LeetCode 2368 - Reachable Nodes With Restrictions

LeetCode Problem 2368 Difficulty: 🟡 Medium Topics: Array, Hash Table, Tree, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution That is a large, highly structured guide. To make sure I target the exact problem and keep the response complete in a single message, can you confirm you want the full solution guide for LeetCode 2368 - Reachable Nodes With Restrictions ? The prompt body currently says 2368 , while some...

Practice › LeetCode › LeetCode 32xx ›

LeetCode 3235 - Check if the Rectangle Corner Is Reachable

LeetCode Problem 3235 Difficulty: 🔴 Hard Topics: Array, Math, Depth-First Search, Breadth-First Search, Union-Find, Geometry Solution Problem Understanding The problem asks whether there is a clear, unobstructed path from the bottom-left corner (0, 0) to the top-right corner (xCorner, yCorner) of a rectangle, such that the path does not touch or go inside any given circles. Each circle is represented by its center (xi, yi) and radius ri . The...

Practice › LeetCode › LeetCode 20xx ›

LeetCode 2076 - Process Restricted Friend Requests

LeetCode Problem 2076 Difficulty: 🔴 Hard Topics: Union-Find, Graph Theory Solution Problem Understanding This problem models a social network with friendship restrictions. We are given n people labeled from 0 to n - 1 . Initially, nobody is connected to anyone else. Over time, friendship requests arrive one by one, and each request must be processed immediately. The important detail is that friendship is transitive. If person A is friends...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 839 - Similar String Groups

LeetCode Problem 839 Difficulty: 🔴 Hard Topics: Array, Hash Table, String, Depth-First Search, Breadth-First Search, Union-Find Solution Problem Understanding The problem asks us to determine the number of similarity groups within a list of strings. Two strings are defined as similar if they are either identical or if we can swap exactly two letters in one string to make it equal to the other. For example, "tars" and "rats" are...

Practice › LeetCode › LeetCode 12xx ›

LeetCode 1258 - Synonymous Sentences

LeetCode Problem 1258 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Backtracking, Sort, Union-Find Solution Problem Understanding This problem asks us to generate all possible synonymous variations of a given sentence based on a list of equivalent word pairs. Each synonym pair indicates that the two words can replace each other interchangeably. The output must include all possible sentences created by substituting words with their synonyms and must be sorted...

Practice › LeetCode › LeetCode 12xx ›

LeetCode 1267 - Count Servers that Communicate

LeetCode Problem 1267 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix, Counting Solution Problem Understanding The problem gives us a two dimensional grid representing a server center. Each cell contains either: 1 , meaning there is a server in that position 0 , meaning the cell is empty A server can communicate with another server if both servers are located in the same row or the same...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 952 - Largest Component Size by Common Factor

LeetCode Problem 952 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Union-Find, Number Theory Solution Problem Understanding The problem asks us to find the largest connected component in a graph derived from an array of unique positive integers nums . Each integer in the array represents a node, and there is an undirected edge between two nodes if the corresponding numbers share a common factor greater than 1. Essentially, numbers...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 547 - Number of Provinces

LeetCode Problem 547 Difficulty: 🟡 Medium Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem is asking us to determine the number of provinces in a network of cities. Each city can be connected directly to other cities, and indirectly through chains of connections. A province is defined as a set of cities that are all directly or indirectly connected, and that has no connections to...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 990 - Satisfiability of Equality Equations

LeetCode Problem 990 Difficulty: 🟡 Medium Topics: Array, String, Union-Find, Graph Theory Solution Problem Understanding The problem is asking us to determine if a set of equations between single-letter variables can all be satisfied simultaneously. Each equation is either of the form "xi==yi" or "xi!=yi" , where xi and yi are lowercase letters from 'a' to 'z' . The task is to assign an integer value to each variable such...

Practice › LeetCode › LeetCode 17xx ›

LeetCode 1722 - Minimize Hamming Distance After Swap Operations

LeetCode Problem 1722 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Union-Find Solution Problem Understanding The problem asks us to find the minimum Hamming distance between two arrays, source and target , after performing any number of swaps on source at positions allowed by allowedSwaps . The Hamming distance is defined as the number of indices i for which source[i] != target[i] . The input consists of two integer arrays of...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 928 - Minimize Malware Spread II

LeetCode Problem 928 Difficulty: 🔴 Hard Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem is about a network of computers represented as an undirected graph using an adjacency matrix. Each node represents a computer, and an edge between two nodes indicates a direct connection. Some nodes are initially infected with malware, and the infection spreads along the network: if a node is...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 737 - Sentence Similarity II

LeetCode Problem 737 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Depth-First Search, Breadth-First Search, Union-Find Solution Problem Understanding This problem asks us to determine whether two sentences are considered similar based on a set of similarity relationships between words. Each sentence is represented as an array of strings, where each string is a single word. We are also given a list of word pairs, where each pair indicates that...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 959 - Regions Cut By Slashes

LeetCode Problem 959 Difficulty: 🟡 Medium Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Let's dive into a full, detailed technical solution guide for LeetCode 959 - Regions Cut By Slashes following your formatting rules. Problem Understanding The problem gives us an n x n grid where each cell contains either a forward slash '/' , a backslash '\\' , or a blank space ' ' ....

Practice › LeetCode › LeetCode 06xx ›

LeetCode 684 - Redundant Connection

LeetCode Problem 684 Difficulty: 🟡 Medium Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem is asking us to identify a redundant edge in a graph that started as a tree. A tree is a connected graph with n nodes and exactly n-1 edges, meaning it has no cycles. The input graph has n nodes and n edges, so by definition, it contains exactly one cycle....

Practice › LeetCode › LeetCode 03xx ›

LeetCode 305 - Number of Islands II

LeetCode Problem 305 Difficulty: 🔴 Hard Topics: Array, Hash Table, Union-Find Solution Problem Understanding The problem gives us an initially empty m x n grid where every cell starts as water. We are then given a sequence of operations in positions , where each operation turns a specific cell from water into land. After every operation, we must determine how many islands currently exist in the grid. An island is...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 399 - Evaluate Division

LeetCode Problem 399 Difficulty: 🟡 Medium Topics: Array, String, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Shortest Path Solution Problem Understanding This problem gives us a collection of equations between variables, where each equation represents a division relationship. For example, if we are given: a / b = 2.0 b / c = 3.0 then we can infer additional relationships such as: a / c = 6.0 c / a...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1697 - Checking Existence of Edge Length Limited Paths

LeetCode Problem 1697 Difficulty: 🔴 Hard Topics: Array, Two Pointers, Union-Find, Graph Theory, Sorting Solution LeetCode 1697 - Checking Existence of Edge Length Limited Paths Problem Understanding This problem gives us an undirected weighted graph with n nodes. Each edge connects two nodes and has a distance value associated with it. We are also given multiple queries, where each query asks whether there exists a path between two nodes such...

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1579 - Remove Max Number of Edges to Keep Graph Fully Traversable

LeetCode Problem 1579 Difficulty: 🔴 Hard Topics: Union-Find, Graph Theory Solution Problem Understanding The problem presents an undirected graph with n nodes and three types of edges: Type 1 for Alice, Type 2 for Bob, and Type 3 for both Alice and Bob. The input edges is an array where each element [type, u, v] represents a bidirectional edge connecting nodes u and v of the specified type. The goal...

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST

LeetCode Problem 1569 Difficulty: 🔴 Hard Topics: Array, Math, Divide and Conquer, Dynamic Programming, Tree, Union-Find, Binary Search Tree, Memoization, Combinatorics, Binary Tree Solution Problem Understanding The problem gives us a permutation of integers from 1 to n , and we insert the numbers into an initially empty Binary Search Tree (BST) in the exact order they appear in the array. A BST has the following property: Values smaller than...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1361 - Validate Binary Tree Nodes

LeetCode Problem 1361 Difficulty: 🟡 Medium Topics: Tree, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Binary Tree Solution Problem Understanding The problem gives us n nodes labeled from 0 to n - 1 . For every node i , we are told which node is its left child and which node is its right child through the arrays leftChild and rightChild . If leftChild[i] = x , then node x...

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1584 - Min Cost to Connect All Points

LeetCode Problem 1584 Difficulty: 🟡 Medium Topics: Array, Union-Find, Graph Theory, Minimum Spanning Tree Solution Problem Understanding This problem asks us to connect all given points on a 2D plane with the minimum possible total cost. Each point is represented as a pair of coordinates [x, y] . The cost of connecting two points is defined as their Manhattan distance: $$|x_i - x_j| + |y_i - y_j|$$ The goal is...

Practice › LeetCode › LeetCode 11xx ›

LeetCode 1101 - The Earliest Moment When Everyone Become Friends

LeetCode Problem 1101 Difficulty: 🟡 Medium Topics: Array, Union-Find, Sorting Solution Problem Understanding The problem is asking us to determine the earliest time at which a group of n people all become mutually acquainted, given a sequence of friendship formation events with timestamps. Each event [timestamp, xi, yi] indicates that person xi and person yi become friends at that exact moment. Friendship is symmetric, meaning if xi is friends with...

Practice › LeetCode › LeetCode 11xx ›

LeetCode 1102 - Path With Maximum Minimum Value

LeetCode Problem 1102 Difficulty: 🟡 Medium Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Union-Find, Heap (Priority Queue), Matrix Solution Problem Understanding The problem asks us to find the maximum possible score of a path from the top-left corner (0, 0) to the bottom-right corner (m-1, n-1) of a 2D grid. Each cell in the grid contains an integer value, and the score of a path is defined as the...

Practice › LeetCode › LeetCode 12xx ›

LeetCode 1202 - Smallest String With Swaps

LeetCode Problem 1202 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Depth-First Search, Breadth-First Search, Union-Find, Sorting Solution Problem Understanding The problem gives us a string s and a list of index pairs called pairs . Each pair [a, b] means we are allowed to swap the characters at positions a and b . The important detail is that swaps can be performed any number of times. This changes the...

Practice › LeetCode › LeetCode 20xx ›

LeetCode 2003 - Smallest Missing Genetic Value in Each Subtree

LeetCode Problem 2003 Difficulty: 🔴 Hard Topics: Array, Dynamic Programming, Tree, Depth-First Search, Union-Find Solution Problem Understanding This problem asks us to compute, for every node in a rooted tree, the smallest positive integer that does not appear in the subtree rooted at that node. We are given two arrays: parents describes the tree structure, and nums contains distinct genetic values assigned to each node. Node 0 is the root,...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 694 - Number of Distinct Islands

LeetCode Problem 694 Difficulty: 🟡 Medium Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union-Find, Sorting, Matrix, Hash Function Solution Problem Understanding The problem gives us a binary matrix called grid , where each cell contains either 0 or 1 . A value of 1 represents land, and a value of 0 represents water. An island is formed by connecting adjacent land cells in the four cardinal directions: up, down,...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 261 - Graph Valid Tree

LeetCode Problem 261 Difficulty: 🟡 Medium Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem asks whether a given undirected graph forms a valid tree. A tree is a special type of graph with two important properties: The graph is fully connected, meaning every node can be reached from every other node. The graph contains no cycles. The input consists of two parts: n , the...

Practice › LeetCode › LeetCode 10xx ›

LeetCode 1020 - Number of Enclaves

LeetCode Problem 1020 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Problem Understanding The problem gives us a binary matrix called grid , where: 0 represents water 1 represents land We can move only in four directions, up, down, left, and right. A land cell is considered an enclave if there is no possible path from that land cell to any boundary cell of the grid....

Practice › LeetCode › LeetCode 11xx ›

LeetCode 1135 - Connecting Cities With Minimum Cost

LeetCode Problem 1135 Difficulty: 🟡 Medium Topics: Union-Find, Graph Theory, Heap (Priority Queue), Minimum Spanning Tree Solution Problem Understanding This problem asks us to connect n cities together using a set of possible bidirectional connections. Each connection has a cost, and our goal is to connect every city while minimizing the total cost. More formally, we are given: An integer n , representing cities labeled from 1 to n A...

Practice › LeetCode › LeetCode 14xx ›

LeetCode 1489 - Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

LeetCode Problem 1489 Difficulty: 🔴 Hard Topics: Union-Find, Graph Theory, Sorting, Minimum Spanning Tree, Strongly Connected Component Solution Problem Understanding The problem gives us a connected, weighted, undirected graph with n vertices and a list of edges. Each edge is represented as [u, v, weight] , meaning there is a bidirectional connection between vertices u and v with the given cost. The goal is not simply to compute one Minimum...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 323 - Number of Connected Components in an Undirected Graph

LeetCode Problem 323 Difficulty: 🟡 Medium Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem asks us to determine how many connected components exist in an undirected graph. A connected component is a group of nodes where every node can reach every other node through some path. If two groups of nodes have no path between them, they belong to different connected components. The input consists...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1631 - Path With Minimum Effort

LeetCode Problem 1631 Difficulty: 🟡 Medium Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Union-Find, Heap (Priority Queue), Matrix Solution Problem Understanding The problem gives us a grid called heights , where each cell contains an integer representing elevation. We start at the top-left corner (0, 0) and want to reach the bottom-right corner (rows - 1, columns - 1) . At each step, we may move in one of...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 947 - Most Stones Removed with Same Row or Column

LeetCode Problem 947 Difficulty: 🟡 Medium Topics: Hash Table, Depth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem gives us a collection of stones placed on a 2D grid. Each stone occupies a unique coordinate (x, y) . A stone can be removed only if there is at least one other stone that shares either the same row or the same column. The goal is to determine the maximum...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 685 - Redundant Connection II

LeetCode Problem 685 Difficulty: 🔴 Hard Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem asks us to identify a redundant edge in a directed graph that originated as a rooted tree. A rooted tree has a single root with all other nodes having exactly one parent. The graph given is initially a tree with n nodes labeled 1 to n , with exactly one extra...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 785 - Is Graph Bipartite?

LeetCode Problem 785 Difficulty: 🟡 Medium Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding The problem asks whether a given undirected graph is bipartite . In simpler terms, we are given a graph represented as an adjacency list graph , where graph[u] lists all nodes directly connected to node u . The goal is to determine if it is possible to split all nodes into two sets...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1632 - Rank Transform of a Matrix

LeetCode Problem 1632 Difficulty: 🔴 Hard Topics: Array, Union-Find, Graph Theory, Topological Sort, Sorting, Matrix Solution Problem Understanding The problem asks us to assign a rank to every element in a matrix while preserving ordering relationships inside rows and columns. For any two elements that share the same row or the same column: If one value is smaller, its rank must also be smaller. If two values are equal, their...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1319 - Number of Operations to Make Network Connected

LeetCode Problem 1319 Difficulty: 🟡 Medium Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding This problem models a computer network as an undirected graph. Each computer is a node, and each ethernet cable is an edge connecting two nodes. The goal is to determine the minimum number of cable rewirings needed to make the entire network fully connected. A network is considered fully connected if every computer...

Practice › LeetCode › LeetCode 17xx ›

LeetCode 1724 - Checking Existence of Edge Length Limited Paths II

LeetCode Problem 1724 Difficulty: 🔴 Hard Topics: Depth-First Search, Union-Find, Graph Theory, Design, Sorting, Heap (Priority Queue), Minimum Spanning Tree Solution LeetCode 1724 - Checking Existence of Edge Length Limited Paths II Problem Understanding This problem gives us an undirected weighted graph with n nodes and a list of edges. Each edge connects two nodes and has an associated distance value. The graph may contain multiple edges between the same...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 200 - Number of Islands

LeetCode Problem 200 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Problem Understanding The problem gives us a two dimensional grid where each cell contains either '1' or '0' . A cell containing '1' represents land, while a cell containing '0' represents water. An island is defined as a group of connected land cells. Two land cells belong to the same island only if they are...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 886 - Possible Bipartition

LeetCode Problem 886 Difficulty: 🟡 Medium Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding This problem asks whether it is possible to divide n people into exactly two groups such that no pair of people who dislike each other end up in the same group. The input contains: An integer n , representing people labeled from 1 to n A list dislikes , where each pair [a,...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1391 - Check if There is a Valid Path in a Grid

LeetCode Problem 1391 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Problem Understanding The problem presents a grid where each cell represents a street segment with a specific orientation, denoted by a number from 1 to 6. Each number encodes which directions the street in that cell connects to neighboring cells. For example, 1 connects left and right, while 2 connects up and down, and the...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 695 - Max Area of Island

LeetCode Problem 695 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Problem Understanding The problem is asking us to find the largest connected area of land in a 2D binary matrix. Each cell in the matrix represents either water ( 0 ) or land ( 1 ). A group of 1 s forms an island if the 1 s are connected 4-directionally (up, down, left, or...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 128 - Longest Consecutive Sequence

LeetCode Problem 128 Difficulty: 🟡 Medium Topics: Array, Hash Table, Union-Find Solution Problem Understanding The problem asks us to find the length of the longest sequence of consecutive integers in an unsorted array. A consecutive sequence means numbers that appear one after another numerically, regardless of their position in the array. The numbers do not need to be adjacent in the input, and the array itself is not sorted. In...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 352 - Data Stream as Disjoint Intervals

LeetCode Problem 352 Difficulty: 🔴 Hard Topics: Hash Table, Binary Search, Union-Find, Design, Data Stream, Ordered Set Solution LeetCode 352 - Data Stream as Disjoint Intervals Problem Understanding This problem asks us to process a stream of non-negative integers and continuously maintain a compact representation of all numbers seen so far. Instead of storing every individual number separately, we want to group consecutive numbers into disjoint intervals. An interval [start,...

Practice › LeetCode › LeetCode 11xx ›

LeetCode 1168 - Optimize Water Distribution in a Village

LeetCode Problem 1168 Difficulty: 🔴 Hard Topics: Union-Find, Graph Theory, Heap (Priority Queue), Minimum Spanning Tree Solution Problem Understanding The problem asks us to supply water to all houses in a village in the most cost-effective way. Each house has two options: either build a well in the house with a fixed cost, or connect the house to another house via pipes, where each pipe has its own construction cost....

Practice › LeetCode › LeetCode 20xx ›

LeetCode 2092 - Find All People With Secret

LeetCode Problem 2092 Difficulty: 🔴 Hard Topics: Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Sorting Solution Problem Understanding The problem describes a network of people who meet at different times. Whenever a person who already knows a secret participates in a meeting, they immediately share the secret with the other participant. The key detail is that sharing is instantaneous within the same timestamp. This means if someone learns the secret...

Practice › LeetCode › LeetCode 10xx ›

LeetCode 1061 - Lexicographically Smallest Equivalent String

LeetCode Problem 1061 Difficulty: 🟡 Medium Topics: String, Union-Find Solution Here is the complete, detailed technical solution guide for LeetCode 1061 following your exact formatting requirements. Problem Understanding The problem requires us to find the lexicographically smallest string that can be obtained from a given baseStr using character equivalencies defined by two strings, s1 and s2 . Each position i in s1 and s2 represents an equivalence relationship between s1[i]...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 924 - Minimize Malware Spread

LeetCode Problem 924 Difficulty: 🔴 Hard Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution Problem Understanding In this problem, we are given an undirected graph represented as an adjacency matrix. Each node represents a computer in a network, and an edge between two nodes means those computers are directly connected. Some subset of nodes is initially infected with malware. Malware spreads through connections, meaning that if...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 827 - Making A Large Island

LeetCode Problem 827 Difficulty: 🔴 Hard Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Problem Understanding This problem asks us to find the largest possible island size in a binary grid after changing at most one 0 into 1 . The grid is an n x n matrix where: 1 represents land 0 represents water An island is formed by land cells connected in the four cardinal directions: up...

Practice › LeetCode › LeetCode 15xx ›

LeetCode 1559 - Detect Cycles in 2D Grid

LeetCode Problem 1559 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Problem Understanding The problem asks us to detect cycles in a 2D grid of characters where all cells in the cycle must contain the same character . A cycle is defined as a path that starts and ends at the same cell and has a length of four or more . Movement is allowed only...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 803 - Bricks Falling When Hit

LeetCode Problem 803 Difficulty: 🔴 Hard Topics: Array, Union-Find, Matrix Solution Problem Understanding This problem asks us to simulate a sequence of brick removals in a 2D grid, while determining how many additional bricks become unstable and fall after each removal. The grid contains only 0 and 1 values: 1 represents a brick 0 represents an empty cell A brick is considered stable if it satisfies at least one of...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 130 - Surrounded Regions

LeetCode Problem 130 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Problem Understanding The problem gives us a two dimensional grid called board , where each cell contains either 'X' or 'O' . The goal is to modify the board in place by capturing every region of 'O' cells that is completely surrounded by 'X' . A region is formed by connecting adjacent 'O' cells horizontally...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 711 - Number of Distinct Islands II

LeetCode Problem 711 Difficulty: 🔴 Hard Topics: Array, Hash Table, Depth-First Search, Breadth-First Search, Union-Find, Sorting, Matrix, Hash Function Solution Problem Understanding In this problem, we are given a binary matrix where each cell contains either 0 or 1 . A value of 1 represents land, while 0 represents water. An island is formed by connecting adjacent land cells in the four cardinal directions: up, down, left, and right. The...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 765 - Couples Holding Hands

LeetCode Problem 765 Difficulty: 🔴 Hard Topics: Greedy, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory Solution LeetCode 765 - Couples Holding Hands Problem Understanding This problem gives us a row of seats represented by the array row , where each value is the ID of the person currently sitting in that seat. The row contains 2n people, meaning there are exactly n couples. The couples are predefined in a very...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1627 - Graph Connectivity With Threshold

LeetCode Problem 1627 Difficulty: 🔴 Hard Topics: Array, Math, Union-Find, Number Theory Solution Problem Understanding The problem gives us n cities labeled from 1 to n . Two cities are directly connected if they share a common divisor that is strictly greater than a given threshold . For example, if threshold = 2 , then cities 6 and 9 are directly connected because they share divisor 3 , and 3...

Practice › LeetCode › LeetCode 12xx ›

LeetCode 1254 - Number of Closed Islands

LeetCode Problem 1254 Difficulty: 🟡 Medium Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix Solution Problem Understanding This problem provides a 2D grid representing a map of land and water. Cells with 0 represent land, and cells with 1 represent water. An island is any contiguous region of land connected horizontally or vertically (not diagonally). A closed island is an island that is entirely surrounded by water on all four...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 778 - Swim in Rising Water

LeetCode Problem 778 Difficulty: 🔴 Hard Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Union-Find, Heap (Priority Queue), Matrix Solution Problem Understanding In this problem, we are given an n x n grid where each cell contains a unique integer representing its elevation. Rain begins falling, and the water level rises over time. At any time t , you are allowed to stand on or move through any cell whose...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 721 - Accounts Merge

LeetCode Problem 721 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Depth-First Search, Breadth-First Search, Union-Find, Sorting Solution Problem Understanding This problem asks us to merge user accounts based on shared email addresses. Each account is represented as a list of strings. The first string is the user's name, and every remaining string is an email address associated with that account. The important detail is that two accounts belong to...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1061: Lexicographically Smallest Equivalent String

Problem Restatement We are given two strings s1 and s2 of the same length, and a string baseStr . From s1 and s2 , we define equivalence classes: s1[i] and s2[i] are equivalent for each i . The equivalence relation is reflexive, symmetric, and transitive. We need to return the lexicographically smallest equivalent string of baseStr using the equivalence classes. The official constraints state that 1 <= s1.length == s2.length...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1020: Number of Enclaves

Problem Restatement We are given a binary matrix grid where 0 represents sea and 1 represents land. A move consists of walking from one land cell to an adjacent (4-directional) land cell. We need to return the number of land cells from which it is impossible to walk off the boundary of the grid. Land cells connected to the boundary are not counted. The official constraints state that m ==...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 924: Minimize Malware Spread

Problem Restatement We are given an undirected graph with n nodes. The graph is represented by an adjacency matrix: graph[i][j] == 1 means node i is directly connected to node j . Some nodes are initially infected with malware. These nodes are listed in: initial Malware spreads through connected edges. If one node in a connected component is infected, eventually every node in that component becomes infected. We must remove...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 947: Most Stones Removed with Same Row or Column

Problem Restatement We are given stones on a 2D plane. Each stone has coordinates: [x, y] A stone can be removed if there is another stone still on the plane that shares either: same row same column Return the maximum number of stones that can be removed. The official statement asks for the largest possible number of removable stones, where each coordinate contains at most one stone. Input and Output...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 839: Similar String Groups

Problem Restatement We are given an array of strings strs . Every string is an anagram of every other string in the array, and all strings have the same length. Two strings are similar if either: They are already equal. We can make them equal by swapping at most two letters in one of the strings. We need to return the number of similar string groups. Similarity is transitive for...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 721: Accounts Merge

Problem Restatement We are given a list of accounts. Each account has this format: [name, email1, email2, ...] Two accounts belong to the same person if they share at least one email address. After merging accounts, each returned account should contain: The person's name. All unique emails belonging to that person, sorted lexicographically. The returned accounts can be in any order. Accounts with the same name do not automatically belong...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 990: Satisfiability of Equality Equations

Problem Restatement We are given an array of equations. Each equation has exactly four characters and is one of two forms: "a==b" "a!=b" Each variable is a lowercase English letter. We need to return True if it is possible to assign integer values to the variables so that all equations are satisfied. Otherwise, return False . For example: ["a==b", "b!=a"] cannot be satisfied, because the first equation says a and...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 959: Regions Cut By Slashes

Problem Restatement We are given an n x n grid. Each cell contains one of three characters: "/" "\\" " " A slash divides a square cell into smaller regions. A blank cell has no internal wall. We need to return how many connected regions exist in the whole grid. The official constraints are: Constraint Value n == grid.length == grid[i].length The grid is square 1 <= n <= 30...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 737: Sentence Similarity II

Problem Restatement We are given two sentences represented as arrays of words: sentence1 sentence2 We are also given a list of similar word pairs: similarPairs Each pair: [x, y] means word x is similar to word y . Two sentences are similar if: They have the same number of words. For every index i , sentence1[i] is similar to sentence2[i] . A word is always similar to itself. Similarity is...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 685: Redundant Connection II

Problem Restatement We are given a directed graph that started as a rooted tree with n nodes. A rooted tree has these properties: Property Meaning One root Exactly one node has no parent One parent per non-root node Every other node has exactly one parent Reachability Every node is reachable from the root No cycle Following directed edges never loops Then one extra directed edge was added. We need to...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 684: Redundant Connection

Problem Restatement We are given an undirected graph. The graph originally started as a tree with n nodes: Property Meaning Connected Every node can be reached No cycles Exactly one path between any two nodes Then one extra edge was added. The input edges contains all edges of the resulting graph. We must return the edge that can be removed so the graph becomes a tree again. If multiple answers...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 547: Number of Provinces

Problem Restatement We are given an n x n matrix called isConnected . There are n cities. If: isConnected[i][j] == 1 then city i and city j are directly connected. A province is a group of cities that are directly or indirectly connected to each other, with no city outside the group connected to them. We need to return the number of provinces. This is the same as counting connected...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 803: Bricks Falling When Hit

Problem Restatement We are given an m x n grid. Each cell is either: Value Meaning 1 Brick 0 Empty space A brick is stable if it is connected to the top row, either directly or through other 4-directionally adjacent stable bricks. We are also given a list of hits. Each hit removes the brick at position (row, col) if a brick exists there. After each hit, some bricks may...

Practice › LeetCode › LeetCode (archived) › LeetCode 09xx ›

LeetCode 952: Largest Component Size by Common Factor

Problem Restatement We are given an array nums of unique positive integers. Each number is a node in a graph. There is an undirected edge between two numbers if they share a common factor greater than 1 . Return the size of the largest connected component in this graph. For example, 6 and 15 are connected because they share factor 3 . The constraints are: Constraint Value nums.length 1 <=...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 827: Making A Large Island

Problem Restatement We are given an n x n binary grid. Each cell is either: Value Meaning 0 Water 1 Land An island is a group of land cells connected in four directions: up, down, left, right We may change at most one 0 into 1 . Return the largest possible island size after doing this operation. If the grid is already all land, we return the size of the...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 399: Evaluate Division

Problem Restatement We are given equations representing division relationships between variables. For example: a / b = 2.0 b / c = 3.0 We are also given queries like: a / c c / a a / e We need to compute the value of each query. If the query cannot be determined from the equations, return: -1.0 The equations are guaranteed to be valid, and there is no contradiction....

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 323: Number of Connected Components in an Undirected Graph

Problem Restatement We are given: n edges There are n nodes labeled: 0 to n - 1 edges describes an undirected graph. Return the number of connected components. A connected component is a maximal group of nodes where every node can reach every other node in the group. The official problem defines the graph as undirected with nodes labeled from 0 to n - 1 . Input and Output Item...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 261: Graph Valid Tree

Problem Restatement We are given: An integer n A list of undirected edges The graph has nodes labeled from 0 to n - 1 . Each edge: [a, b] means there is an undirected connection between node a and node b . We need to return True if these edges form a valid tree. Otherwise, return False . A valid tree must satisfy two properties: Property Meaning Connected Every node...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 130: Surrounded Regions

Problem Restatement We are given an m x n board containing only two characters: Character Meaning "X" Wall or blocking cell "O" Open cell We need to capture every region of "O" cells that is completely surrounded by "X" cells. A region is connected 4-directionally, meaning cells connect through up, down, left, and right. Diagonal connection does not count. To capture a surrounded region, we flip every "O" in that...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 305: Number of Islands II

Problem Restatement We are given an empty m x n grid filled with water. Each operation turns one cell into land. After every operation, return the current number of islands. An island is a group of connected land cells connected horizontally or vertically. The official problem defines: Value Meaning 0 Water 1 Land The grid starts entirely with water. For each position in positions , we add land at that...

Wiki › Algorithms › 02. Data Structures › 2. Advanced Data Structures and Operations ›

2.5 Disjoint Set Union Variants

2.5 Disjoint set union variants, 35 index slug name 1 disjoint-set-union Disjoint Set Union 2 union-find Union Find 3 dsu-make-set Make Set 4 dsu-find Find 5 dsu-union Union 6 path-compression Path Compression 7 union-by-rank Union by Rank 8 union-by-size Union by Size 9 dsu-rollback Rollback DSU 10 dsu-persistent Persistent DSU 11 dsu-parity Parity DSU 12 dsu-weighted Weighted DSU 13 dsu-bipartite-check Bipartite Check 14 dsu-component-size Component Size 15 dsu-component-sum Component Sum...

#union-find

LeetCode 3666 - Minimum Operations to Equalize Binary String

LeetCode 3910 - Count Connected Subgraphs with Even Node Sum

LeetCode 3887 - Incremental Even-Weighted Cycle Queries

LeetCode 3613 - Minimize Maximum Component Cost

LeetCode 3608 - Minimum Time for K Connected Components

LeetCode 3600 - Maximize Spanning Tree Stability with Upgrades

LeetCode 3873 - Maximum Points Activated with One Addition

LeetCode 3710 - Maximum Partition Factor

LeetCode 3695 - Maximize Alternating Sum Using Swaps

LeetCode 3619 - Count Islands With Total Value Divisible by K

LeetCode 3607 - Power Grid Maintenance

LeetCode 3532 - Path Existence Queries in a Graph I

LeetCode 3493 - Properties Graph

LeetCode 3108 - Minimum Cost Walk in Weighted Graph

LeetCode 2573 - Find the String with LCP

LeetCode 2658 - Maximum Number of Fish in a Grid

LeetCode 2852 - Sum of Remoteness of All Cells

LeetCode 2382 - Maximum Segment Sum After Removals

LeetCode 2492 - Minimum Score of a Path Between Two Cities

LeetCode 2709 - Greatest Common Divisor Traversal

LeetCode 2334 - Subarray With Elements Greater Than Varying Threshold

LeetCode 2157 - Groups of Strings

LeetCode 3378 - Count Connected Components in LCM Graph

LeetCode 2424 - Longest Uploaded Prefix

LeetCode 2503 - Maximum Number of Points From Grid Queries

LeetCode 1998 - GCD Sort of an Array

LeetCode 2612 - Minimum Reverse Operations

LeetCode 2685 - Count the Number of Complete Components

LeetCode 2371 - Minimize Maximum Value in a Grid

LeetCode 2948 - Make Lexicographically Smallest Array by Swapping Elements

LeetCode 3383 - Minimum Runes to Add to Cast Spell

LeetCode 1971 - Find if Path Exists in Graph

LeetCode 1905 - Count Sub Islands

LeetCode 1970 - Last Day Where You Can Still Cross

LeetCode 2782 - Number of Unique Categories

LeetCode 2307 - Check for Contradictions in Equations

LeetCode 2617 - Minimum Number of Visited Cells in a Grid

LeetCode 2812 - Find the Safest Path in a Grid

LeetCode 2316 - Count Unreachable Pairs of Nodes in an Undirected Graph

LeetCode 2421 - Number of Good Paths

LeetCode 2493 - Divide Nodes Into the Maximum Number of Groups

LeetCode 2368 - Reachable Nodes With Restrictions

LeetCode 3235 - Check if the Rectangle Corner Is Reachable

LeetCode 2076 - Process Restricted Friend Requests

LeetCode 839 - Similar String Groups

LeetCode 1258 - Synonymous Sentences

LeetCode 1267 - Count Servers that Communicate

LeetCode 952 - Largest Component Size by Common Factor

LeetCode 547 - Number of Provinces

LeetCode 990 - Satisfiability of Equality Equations

LeetCode 1722 - Minimize Hamming Distance After Swap Operations

LeetCode 928 - Minimize Malware Spread II

LeetCode 737 - Sentence Similarity II

LeetCode 959 - Regions Cut By Slashes

LeetCode 684 - Redundant Connection

LeetCode 305 - Number of Islands II

LeetCode 399 - Evaluate Division

LeetCode 1697 - Checking Existence of Edge Length Limited Paths

LeetCode 1579 - Remove Max Number of Edges to Keep Graph Fully Traversable

LeetCode 1569 - Number of Ways to Reorder Array to Get Same BST

LeetCode 1361 - Validate Binary Tree Nodes

LeetCode 1584 - Min Cost to Connect All Points

LeetCode 1101 - The Earliest Moment When Everyone Become Friends

LeetCode 1102 - Path With Maximum Minimum Value

LeetCode 1202 - Smallest String With Swaps

LeetCode 2003 - Smallest Missing Genetic Value in Each Subtree

LeetCode 694 - Number of Distinct Islands

LeetCode 261 - Graph Valid Tree

LeetCode 1020 - Number of Enclaves

LeetCode 1135 - Connecting Cities With Minimum Cost

LeetCode 1489 - Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

LeetCode 323 - Number of Connected Components in an Undirected Graph

LeetCode 1631 - Path With Minimum Effort

LeetCode 947 - Most Stones Removed with Same Row or Column

LeetCode 685 - Redundant Connection II

LeetCode 785 - Is Graph Bipartite?

LeetCode 1632 - Rank Transform of a Matrix

LeetCode 1319 - Number of Operations to Make Network Connected

LeetCode 1724 - Checking Existence of Edge Length Limited Paths II