LeetCode 2793: Status of Flight Tickets Solution

Master LeetCode problem 2793 (Status of Flight Tickets), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2793. Status of Flight Tickets

Hard

Problem Explanation

Explanation:

The problem can be solved using Union-Find (Disjoint Set Union) data structure. We initially create a disjoint set for each passenger and connect them based on their ticket information. Then we can query the status of any two passengers to check if they are on the same flight.

Create a Union-Find data structure with the following operations:
- find: Find the root of the set to which a passenger belongs.
- union: Connect two sets together.
Iterate through the given flight tickets and for each ticket, union the passengers based on their ticket information.
To query the status of two passengers, find their roots using the find operation and check if they are the same.

Time Complexity:

The time complexity for Union-Find operations is typically O(α(n)), where α(n) is the inverse Ackermann function.
The overall time complexity for processing all flight tickets and queries is O(T + Q * α(n)), where T is the number of flight tickets and Q is the number of queries.

Space Complexity:

O(n) where n is the number of passengers.

Solution Code

class UnionFind {
    int[] parent;

    public UnionFind(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }
}

public class FlightTicketsStatus {
    public boolean isSameFlight(int[][] tickets, int passenger1, int passenger2) {
        int n = tickets.length;
        UnionFind uf = new UnionFind(n);

        for (int i = 0; i < n; i++) {
            uf.union(tickets[i][0], tickets[i][1]);
        }

        return uf.find(passenger1) == uf.find(passenger2);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2793 (Status of Flight Tickets)?

This page provides optimized solutions for LeetCode problem 2793 (Status of Flight Tickets) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2793 (Status of Flight Tickets)?

The time complexity for LeetCode 2793 (Status of Flight Tickets) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2793 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2793 in Java, C++, or Python.

Back to LeetCode Solutions