Hackerearth | OA | Happy Neighbourhood

Round 1

Questions: The other question asked in the same OA - Hackerearth or OA or The Prom

Happy Neighbourhood

In a neighborhood, there are N empty houses numbered from 1 to N arranged in a line. Each day, starting from day 1, one house will be occupied by residents. The sequence of occupied houses is given as a permutation of length N. On the ith day, the house with the number given by the ith element of the permutation will be occupied.

The neighborhood will be considered happy if there is at least one set of consecutive occupied houses. On which day will the neighborhood become happy?

Note: A permutation of length N is an array of N integers where each element is between 1 and N, with no repetitions.

Function Description

Complete the function solve. This function takes the following 3 parameters and returns the required answer.

• N: Represents the number of houses
• M: Represents the number of consecutive houses needed
• house: Represents an array indicating the house that will be filled on each day

Input format for custom testing

• The first line contains N denoting the number of houses.
• The second line contains M denoting the number of consecutive houses needed.
• The third line contains an array house denoting the house that will be filled on each day.

Output format

Print a single integer representing the first day on which the neighbourhood becomes happy.

Constraints 1 ≤ N ≤ 10^5
1 ≤ M ≤ N
1 ≤ house[i] ≤ N

Sample Input         Sample Output
3                    1
1
3 2 1

Explanation Given

• N = 3
• M = 1
• house = [3, 2, 1]

Output

1

Approach

On day 1, house 3 is filled. Only 1 consecutive house is needed, so the neighbourhood becomes happy.

Note:
Your code must be able to print the sample output from the provided sample input. However, your code is run against multiple hidden test cases. Therefore, your code must pass these hidden test cases to solve the problem statement.

Limits Time Limit: 1.0 sec(s) for each input file
Memory Limit: 256 MB
Source Limit: 1024 KB

Test case 1

Input                       Expected Output
10                          10
8
8 4 9 10 3 1 7 2 6 5

Test case 2

Input                                                      Expected Output
20                                                         5
2
16 12 14 7 11 13 15 4 1 20 9 3 10 8 6 2 17 19 18 5

Test case 3

Input                Expected Output
5                    5
5
5 4 1 2 3

Working Solution

private static class UnionFind {
    int[] size;
    int[] parent;

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

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

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (size[rootX] < size[rootY]) {
                int temp = rootX;
                rootX = rootY;
                rootY = temp;
            }
            parent[rootY] = rootX;
            size[rootX] += size[rootY];
        }
    }

    public int componentSize(int x) {
        return size[find(x)];
    }
}

public class Main {
    public static int solve(int N, int M, int[] house) {
        UnionFind uf = new UnionFind(N);
        boolean[] occupied = new boolean[N + 1]; // Track which houses are occupied
    
        for (int day = 0; day < N; day++) {
            int currentHouse = house[day];
            occupied[currentHouse] = true;
    
            // Connect current house with its left and right neighbors
            if (currentHouse > 1 && occupied[currentHouse - 1]) {
                uf.union(currentHouse, currentHouse - 1);
            }
            if (currentHouse < N && occupied[currentHouse + 1]) {
                uf.union(currentHouse, currentHouse + 1);
            }
    
            // Check if there is a component with size at least M
            if (uf.componentSize(currentHouse) >= M) {
                return day + 1; // Return the day (1-based index)
            }
        }
    
        return -1; // Should not be reached for valid inputs
    }
    
    public static void main(String[] args) {
        int N = 20;
        int M = 2;
        int[] house = {16, 12, 14, 7, 11, 13, 15, 4, 1, 20, 9, 3, 10, 8, 6, 2, 17, 19, 18, 5};
        System.out.println(solve(N, M, house));
    }
}