FastPrepThe Prom
Problems/The Prom

The Prom

HackerEarth logoHackerEarth● EasyOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

N people stand in a line with IDs from 1 to N to enter their high school's prom. They arrive one at a time in ID order, so person 1 is at the front of the line.

You are given a string S of length N. Character S[i - 1] is '0' if person i is a girl and '1' if person i is a boy. When a boy arrives, he pairs up with the girl standing immediately ahead of him in the line, that is, the girl with the largest ID among the girls who arrived before him and are still in the line. They then leave the line together to go to the dance floor. If no girl is left in the line ahead of him, the boy cannot get a date.

Return an integer array with one entry for each boy, in order of arrival: the ID of the girl he dances with, or -1 if he cannot get a date. If there are no boys, return an empty array.

Complete the function solve. It takes the following 2 parameters:

  • N: the number of people
  • S: the binary string of genders

Function

solve(N: int, S: String) → int[]

Examples

Example 1

N = 3S = "011"return = [1, -1]

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

N = 11S = "10001111110"return = [-1, 4, 3, 2, -1, -1, -1]

Person 1 is a boy with no girl ahead, so -1. Girls 2, 3 and 4 join the line. Boy 5 takes girl 4, the closest girl ahead of him. Boy 6 then takes girl 3 and boy 7 takes girl 2. Boys 8, 9 and 10 find no girl left, so each gets -1. Girl 11 arrives last and is not paired.

Example 3

N = 7S = "0000100"return = [4]

Girls 1 to 4 join the line. The only boy, person 5, takes girl 4, who is directly ahead of him. Girls 6 and 7 come later and are not paired.

Constraints

  • 1 ≤ N ≤ 105
  • S.length = N
  • Each character of S is '0' or '1'.

More HackerEarth interview questions

  • Happy NeighbourhoodOA · Seen Oct 2024

Similar questions at other companies

  • Validate a Bracket SequenceInMobi · OAInMobi interview questions
  • Valid ParenthesesBlackRock · OABlackRock interview questions
  • Valid ParenthesesVanguard · OAVanguard interview questions
  • Valid Bracket SequenceNVIDIA · OA · PHONE SCREENNVIDIA interview questions
  • Get Final StringIBM · OAIBM interview questions
  • Backspace String CompareGoldman Sachs · OAGoldman Sachs interview questions
  • Compare Character Arrays with BackspacesOdoo · OAOdoo interview questions
  • Eliminate SubstringJP Morgan Chase · OAJP Morgan Chase interview questions
  • Balancing ParenthesesOracle · OAOracle interview questions
  • Collapse Equal Adjacent PairsHudson River Trading · OAHudson River Trading interview questions
See HackerEarth hiring insights
Saved
class Solution {
    public int[] solve(int N, String S) {
      // write your code here
    }

}
Checking account…