In a neighbourhood, 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 neighbourhood will be considered happy if there is at least one set of consecutive occupied houses. On which day will the neighbourhood 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
Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code.
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.
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 KBScoring Score is assigned if any testcase passes
Constraints
1 ≤ N ≤ 10⁵1 ≤ M ≤ N1 ≤ house[i] ≤ N
Example 1
Input:
N = 3
M = 1
house = [3, 2, 1]Output:
1Explanation: On day 1, house 3 is filled. Only 1 consecutive house is needed, so the neighbourhood becomes happy.
Example 2
Input:
N = 10
M = 8
house = [8, 4, 9, 10, 3, 1, 7, 2, 6, 5]Output:
10Explanation: Will add once find reliable reference:)
Example 3
Input:
N = 20
M = 2
house = [16, 12, 14, 7, 11, 13, 15, 4, 1, 20, 9, 3, 10, 8, 6, 2, 17, 19, 18, 5]Output:
5Explanation: Will add once find reliable reference:)
Example 4
Input:
N = 5
M = 5
house = [5, 4, 1, 2, 3]Output:
5Explanation: Will add once find reliable reference:)
解法
并查集维护连续段：用 occupied[] 数组，每填入 house[i] 就 union 它与左右已占据的邻居，并跟踪合并后段的长度，最大段长 ≥ M 则返回 i+1。时间 O(N α(N))。
from typing import List
def solve(N: int, M: int, house: List[int]) -> int:
parent = list(range(N + 2))
size = [0] * (N + 2)
occupied = [False] * (N + 2)
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb:
return size[ra]
parent[ra] = rb
size[rb] += size[ra]
return size[rb]
best = 0
for day, h in enumerate(house, 1):
occupied[h] = True
size[h] = 1
cur = 1
if h > 1 and occupied[h - 1]:
cur = union(h, h - 1)
if h < N and occupied[h + 1]:
cur = union(h, h + 1)
best = max(best, cur)
if best >= M:
return day
return -1class Solution {
int[] parent, size; boolean[] occ;
int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
int union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return size[ra];
parent[ra] = rb; size[rb] += size[ra]; return size[rb];
}
public int solve(int N, int M, int[] house) {
parent = new int[N + 2]; size = new int[N + 2]; occ = new boolean[N + 2];
for (int i = 0; i < N + 2; i++) parent[i] = i;
int best = 0;
for (int day = 0; day < house.length; day++) {
int h = house[day]; occ[h] = true; size[h] = 1; int cur = 1;
if (h > 1 && occ[h - 1]) cur = union(h, h - 1);
if (h < N && occ[h + 1]) cur = union(h, h + 1);
best = Math.max(best, cur);
if (best >= M) return day + 1;
}
return -1;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
vector<int> parent, sz; vector<bool> occ;
int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
int unite(int a, int b) { int ra=find(a), rb=find(b); if (ra==rb) return sz[ra]; parent[ra]=rb; sz[rb]+=sz[ra]; return sz[rb]; }
public:
int solve(int N, int M, vector<int>& house) {
parent.resize(N + 2); sz.assign(N + 2, 0); occ.assign(N + 2, false);
iota(parent.begin(), parent.end(), 0);
int best = 0;
for (int day = 0; day < (int)house.size(); day++) {
int h = house[day]; occ[h] = true; sz[h] = 1; int cur = 1;
if (h > 1 && occ[h - 1]) cur = unite(h, h - 1);
if (h < N && occ[h + 1]) cur = unite(h, h + 1);
best = max(best, cur);
if (best >= M) return day + 1;
}
return -1;
}
};02The Prom
N people stand in a line with IDs from 1 to N to enter their high school's prom.
Given a string S, where '0' indicates girls and '1' indicates a boy. When a boy arrives, he pairs up with the girl standing immediately ahead him in line. They then leave the line to go to the dance floor.
To ensure that everyone at the prom gets one dance, each boy finds the ID of the girl who he danced with. If a boy cannot go on a date, the answer is -1.
Function Description
Complete the function solve. This function takes the following 2 parameters:
N: Represents the number of peopleS: Represents the binary string denoting the genders Input format for custom testing Note: Use this input format if you are testing against custom input or writing code in a language where we don't provide boilerplate code. The first line contains a single integer N denoting the number of people. The second line contains a binary string S of size N denoting the genders of the people. Output Format Print space-separated integers denoting the IDs of the girls. 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 Scoring Score is assigned if any testcase passes
Constraints
- 1 ≤ N ≤ 10⁵
- S[i] ∈ {0, 1} ∀ i ∈ [1,N]
Example 1
Input:
N = 3
S = "011"Output:
[1, -1]Explanation: Given:
- N = 3
- S = "011" Approach:
- Person 1 (girl) joins the line
- Person 2 (boy) looks for a girl standing ahead (person 1) and both of them go on a date.
- Person 3 (boy) looks for a girl, but as there is no girl standing, the answer is -1. So answer = [1, -1]
Example 2
Input:
N = 11
S = "10001111110"Output:
[-1 4 3 2 -1 -1 -1]Explanation: Will add once find reliable reference :)
Example 3
Input:
N = 7
S = "0000100"Output:
[4]Explanation: Will add once find reliable reference :)
解法
栈维护当前在队伍中尚未配对的女孩 id。扫描 S：'0' 入栈；'1' 若栈非空则弹栈得到与之配对的女孩 id，记录到答案；若栈空则答案添 -1。时间 O(N)。
from typing import List
def solve(N: int, S: str) -> List[int]:
stack: List[int] = []
out: List[int] = []
for i, c in enumerate(S, 1):
if c == '0':
stack.append(i)
else:
out.append(stack.pop() if stack else -1)
return outimport java.util.*;
class Solution {
public int[] solve(int N, String S) {
Deque<Integer> stack = new ArrayDeque<>();
List<Integer> out = new ArrayList<>();
for (int i = 0; i < N; i++) {
char c = S.charAt(i);
if (c == '0') stack.push(i + 1);
else out.add(stack.isEmpty() ? -1 : stack.pop());
}
return out.stream().mapToInt(Integer::intValue).toArray();
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> solve(int N, string S) {
vector<int> stack, out;
for (int i = 0; i < N; i++) {
if (S[i] == '0') stack.push_back(i + 1);
else { if (stack.empty()) out.push_back(-1); else { out.push_back(stack.back()); stack.pop_back(); } }
}
return out;
}
};