2025 September 20 Problems

[daryl...@gmail.com]

Feel free to work on any of the problems you want; we'll have people present their solutions at 11:30.

Please post your solutions to this thread so others can use this as a reference.

2900. Longest Unequal Adjacent Groups Subsequence I Easy Easy 67.2%

3243. Shortest Distance After Road Addition Queries I Medium 61.8%

3244. Shortest Distance After Road Addition Queries II Hard 25.9%

Please download and import the following iCalendar (.ics) files to your calendar system.

Weekly: https://us04web.zoom.us/meeting/upIqc-6upj8sGt0O2fJXTw2gC4FxRMQ-iqAT/ics?icsToken=98tyKu6uqT8tHNyRthmOR7YAB4-gKO7xiCldjbcNs03jKRhndVHxFbZkKoBSIZXZ

Join Zoom Meeting (Meeting starts at 11:30)
https://us04web.zoom.us/j/76747684609?pwd=HOCapO7jjK0rifPlKvV9CxWFn5lLJn.1

Meeting ID: 767 4768 4609

[FloM]

2900. Longest Unequal Adjacent Groups Subsequence I Easy Easy 67.2%

class Solution {

public:

vector<string> getLongestSubsequence(vector<string>& words, vector<int>& groups) {

vector<string> ans = {words[0]};

int cur = groups[0];

for(int ii=1; ii<groups.size(); ++ii)

{

if (cur != groups[ii])

{

ans.push_back(words[ii]);

cur = groups[ii];

}

}

return ans;

}

};

[FloM]

3243. Shortest Distance After Road Addition Queries I Medium 61.8%

Just did this one last week. Time: O(q * n), Memory: O(n*q). q = num of queries, n = num of cities.

class Solution {

public:

vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {

vector<int> dist(n);

iota(dist.begin(), dist.end(), 0);

vector<vector<int>> adjList(n, vector<int>{});

for(int ii=0; ii<n-1; ++ii)

{

adjList[ii].push_back(ii+1);

}

vector<int> ans{};

for(int ii=0; ii<queries.size(); ++ii)

{

adjList[queries[ii][0]].push_back(queries[ii][1]);

queue<int> q{};

q.push(queries[ii][0]);

while(!q.empty())

{

int u = q.front();

q.pop();

for(int adj : adjList[u])

{

if (dist[adj] > dist[u] + 1)

{

dist[adj] = dist[u] + 1;

q.push(adj);

}

}

}

ans.push_back(dist[n-1]);

}

return ans;

}

};

[Anuj Patnaik]

class Solution:

def getLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:

subseq = [words[0]]

for i in range(1, len(words)):

if groups[i] != groups[i - 1]:

subseq.append(words[i])

return subseq

[Allen S.]

tc: O(n)
sc: O(1)

func getLongestSubsequence(words []string, groups []int) []string {

var res []string

lastGroup := -1

for i, v := range groups {

if v != lastGroup {

res = append(res, words[i])

lastGroup = v

}

}

return res

}

[Eli Manzo]

Won't be able to join due to family emergencies, but I wanted to get the consistency going
Time: O(2^n *n)
Space: O(2^n * n)

class Solution:

  def generateUnequalSubsequence(self, groups):

    res = []

    subsequence = []

    def backtrack(index):

      if index == len(groups):

        res.append(subsequence[:])

        return

     

      if subsequence and groups[index] == groups[subsequence[-1]]:

        backtrack(index + 1)

        return

      subsequence.append(index)

      backtrack(index + 1)

      subsequence.pop()

      backtrack(index + 1)

    backtrack(0)

    return res

  def getLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:

    subsequences = self.generateUnequalSubsequence(groups)

    longest = max(subsequences, key=len)

    return [words[i] for i in longest]

Key: no two consecutive elements can come from the same group. 
Time:O(n)
Space:O(n)

class Solution:

  def getLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:

    res = [words[0]]

    for i in range(1, len(groups)):

      if groups[i] == groups[i - 1]:

        continue

      res.append(words[i])

    return res

[Sourabh Majumdar]

Shortest Distance After Road Addition Queries 1 (using the priority queue)

class Solution {

public:

vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {

std::unordered_map<int, std::vector<int>> graph;

std::vector<int> min_distance_to_city(n, std::numeric_limits<int>::max());

min_distance_to_city[0] = 0;

// create the normal connctions (directed edges).

for(int node = 0; node < (n - 1); node++) {

graph[node].push_back(node + 1);

min_distance_to_city[node] = node;

}

min_distance_to_city[n - 1] = n - 1;

// at each query

std::vector<int> shortest_distance_to_last_node;

// Define City{...}, city_comparator()

struct City{

int city;

int distance;

};

auto city_comparator = [](City& city1, City& city2) {

return city1.distance > city2.distance;

};

auto dijkstra = [&](int source) {

std::priority_queue<City, std::vector<City>, decltype(city_comparator)> cities_by_distance;

cities_by_distance.push(

City{

.city = source,

.distance = min_distance_to_city[source]

}

);

std::unordered_set<int> visited_cities;

while(!cities_by_distance.empty()) {

City current_city = cities_by_distance.top();

int city_value = current_city.city;

int city_distance = current_city.distance;

cities_by_distance.pop();

if (visited_cities.contains(city_value)) {

continue;

}

for(auto neighbor : graph[city_value]) {

if (min_distance_to_city[neighbor] > (min_distance_to_city[city_value] + 1)) {

// insert this city into the queue

min_distance_to_city[neighbor] = (

min_distance_to_city[city_value] + 1

);

cities_by_distance.push(

City{

.city = neighbor,

.distance = min_distance_to_city[neighbor]

}

);

}

}

visited_cities.insert(city_value);

}

};

for(auto query : queries) {

int source = query[0];

int destination = query[1];

// make the connection

graph[source].push_back(destination);

// run dijkstra

dijkstra(source);

shortest_distance_to_last_node.push_back(min_distance_to_city[n - 1]);

}

return shortest_distance_to_last_node;

}

}; But now, note that std::set<> can also work here, because it is a BST under the hood.

class Solution {

public:

vector<int> shortestDistanceAfterQueries(int n, vector<vector<int>>& queries) {

std::unordered_map<int, std::vector<int>> graph;

std::vector<int> min_distance_to_city(n, std::numeric_limits<int>::max());

min_distance_to_city[0] = 0;

// create the normal connctions (directed edges).

for(int node = 0; node < (n - 1); node++) {

graph[node].push_back(node + 1);

min_distance_to_city[node] = node;

}

min_distance_to_city[n - 1] = n - 1;

// at each query

std::vector<int> shortest_distance_to_last_node;

// Define City{...}, city_comparator()

struct City{

int city;

int distance;

};

auto city_comparator = [](const City& city1, const City& city2) {

if (city1.distance == city2.distance) {

return city1.city < city2.city;

}

return city1.distance < city2.distance;

};

auto dijkstra = [&](int source) {

// imlementation using the set

// std::priority_queue<City, std::vector<City>, decltype(city_comparator)> cities_by_distance;

std::set<City, decltype(city_comparator)> cities_by_distance;

// cities_by_distance.push(

// City{

// .city = source,

// .distance = min_distance_to_city[source]

// }

// );

cities_by_distance.insert(

City{

.city = source,

.distance = min_distance_to_city[source]

}

);

std::unordered_set<int> visited_cities;

while(!cities_by_distance.empty()) {

// City current_city = cities_by_distance.top();

// int city_value = current_city.city;

// int city_distance = current_city.distance;

// cities_by_distance.pop();

City current_city = *cities_by_distance.begin();

cities_by_distance.erase(current_city);

// We probably do not need it in the case of a set.

// if (visited_cities.contains(city_value)) {

// continue;

// }

int city_value = current_city.city;

for(auto neighbor : graph[city_value]) {

if (min_distance_to_city[neighbor] > (min_distance_to_city[city_value] + 1)) {

// find and erase the city

// This is also O(logn)

cities_by_distance.erase(

City{

.city = neighbor,

.distance = min_distance_to_city[neighbor]

}

);

min_distance_to_city[neighbor] = (

min_distance_to_city[city_value] + 1

);

// cities_by_distance.push(

// City{

// .city = neighbor,

// .distance = min_distance_to_city[neighbor]

// }

// );

// insert this city into the queue

// I am assuming that this is O(logn)

cities_by_distance.insert(

City{

.city = neighbor,

.distance = min_distance_to_city[neighbor]

}

);

}

}

// visited_cities.insert(city_value);

}

};

for(auto query : queries) {

int source = query[0];

int destination = query[1];

// make the connection

graph[source].push_back(destination);

// run dijkstra

dijkstra(source);

shortest_distance_to_last_node.push_back(min_distance_to_city[n - 1]);

}

return shortest_distance_to_last_node;

}

}; But in terms of space complexity (where the claim is that set might save space), we did not gain much (deep sighs)

[Sourabh Majumdar]

The Longest Unequal Adjacent Groups Subsequence I

We just enumerate and pick indexes in alternating fashion, pick a group with value 0 after picking a group with value 1. This is a greedy solution, because it can be proven that our greedy choice (picking the first available index with target group value) will always choose the first available such index. class Solution {

public:

vector<string> getLongestSubsequence(vector<string>& words, vector<int>& groups) {

std::queue<int> selected_indexes;

int target_group = groups[0] ^ 1;

selected_indexes.push(0);

for(int index = 1; index < groups.size(); index++) {

if (groups[index] == target_group) {

selected_indexes.push(index);

target_group ^= 1;

}

}

std::vector<std::string> subsequence;

while(!selected_indexes.empty()) {

int selected_index = selected_indexes.front();

selected_indexes.pop();

subsequence.push_back(words[selected_index]);

}

return subsequence;

}

};

[Nico Wong]

class Solution:

    def getLongestSubsequence(self, words: List[str], groups: List[int]) -> List[str]:

        mostRecentGroup = -1

        out = []

        for word, group in zip(words, groups):

            if group != mostRecentGroup:

                mostRecentGroup = group

                out.append(word)

        return out

        # 10 minutes

On Saturday, September 20, 2025 at 9:42:48 AM UTC-7 daryl...@gmail.com wrote:

[Nico Wong]

I saw a message from Olivia that she wants to do LeetCode after at the library, but I can't find it anymore.

--
whatspp group: http://whatsapp.techbayarea.us/
---
You received this message because you are subscribed to the Google Groups "leetcode-meetup" group.
To unsubscribe from this group and stop receiving emails from it, send an email to leetcode-meet...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/leetcode-meetup/4c81ba18-982a-4cb8-a834-6d28b48c2054n%40googlegroups.com.

[Jagrut]

2900. Longest Unequal Adjacent Groups Subsequence I Easy Easy 67.2%

function getLongestSubsequence(words: string[], groups: number[]): string[] {

const result: string[] = [];

var v:number = -1;

for (let i: number = 0; i < words.length; i++) {

if (groups[i] !== v) {

v = groups[i];

result.push(words[i]);

}

}

return result;

};

3243. Shortest Distance After Road Addition Queries I Medium 61.8%

function shortestDistanceAfterQueries(n: number, queries: number[][]): number[] {

const result: number[] = new Array<number>(queries.length);

const graph: Map<number, number[]> = _buildGraph(n);

for (const [idx, query] of queries.entries()) {

_addEdge(graph, query[0], query[1]);

result[idx] = (_bfs(graph, 0, n - 1));

}

return result;

};

function _bfs(g: Map<number, number[]>, current: number, target: number) {

var steps = 0;

const q: number[] = [];

const seen: Set<number> = new Set();

q.push(current);

seen.add(current);

while (q.length > 0) {

const size: number = q.length;

for (let i = 0; i < size; i++) {

const node: number = q.shift();

for (const neighbor of g.get(node)) {

if (neighbor === target) {

return steps + 1;

}

if (!seen.has(neighbor)) {

q.push(neighbor);

seen.add(neighbor);

}

}

}

steps += 1;

}

return -1; // no answer found, this should not happen

}

function _buildGraph(n: number): Map<number, number[]> {

const g = new Map<number, number[]>();

for (let i: number = 0; i < n - 1; i++) {

g.set(i, [i + 1]);

}

return g;

}

function _addEdge(g: Map<number, number[]>, from: number, to: number): void {

g.get(from).push(to);

}

3244. Shortest Distance After Road Addition Queries II Hard 25.9%

function shortestDistanceAfterQueries(n: number, queries: number[][]): number[] {

const result: number[] = new Array(queries.length);

let pathLength = n - 1;

// index -> city it is connected to, represents the graph

const connections: number[] = Array.from({ length: n - 1 }, (_, i) => i + 1);

for (const [idx, query] of queries.entries()) {

const from = query[0];

const to = query[1];

if ((connections[from] > 0) && (connections[from] < to)) {

// shorter path possible between 'from' and 'to'

let currentEnd = connections[from];

while (currentEnd < to) {

pathLength -= 1;

const next = connections[currentEnd];

connections[currentEnd] = 0; // removed

currentEnd = next;

}

connections[from] = to;

}

result[idx] = pathLength;

}

return result;

};

--

Jagrut

[Allen S.]

time: n * (n+q)
space: n + q
logic: BFS each version of graph

func shortestDistanceAfterQueries(n int, queries [][]int) []int {

res := make([]int, len(queries))

graph := make([][]int, n) // adjacency table

// initialize the adj table

for node := 0; node < len(graph) - 1; node++ {

graph[node] = append(graph[node], node + 1)

}

for i, v := range queries {

graph[v[0]] = append(graph[v[0]], v[1]) // add new route

res[i] = BFS(graph, n)

}

return res

}

func BFS(graph [][]int, n int) int {

q := []int{0} // queue

seen := map[int]bool{0:true}

dist := 0

for len(q) > 0 {

size := len(q)

for range size {

now := q[0]

q = q[1:]

if now == n - 1 {

return dist

}

for _, nei := range graph[now] {

if !seen[nei] {

seen[now] = true

q = append(q, nei)

}

}

}

dist++

}

return dist

}

On Saturday, September 20, 2025 at 2:15:20 PM UTC-7 nico...@gmail.com wrote: