Largest Consistent Visiting Group
Updated
Problem statement
There are k friends, numbered from 1 to k. For n days, you write down the order in which the friends visited you. You get these orders as a 2D array orders with n rows: orders[d] lists all k friends in the order they visited on day d.
Pick a group of friends. The group is consistent when every two friends in it keep the same order on every day: if friend a visits before friend b on one day, then a visits before b on all n days.
The friends in a group do not need to visit one right after another. Other friends may visit between them.
Return the size of the largest consistent group. A group of one friend is always consistent.
Function
largestConsistentGroup(orders: int[][]) → intExamples
Example 1
orders = [[1,2,3],[2,1,3]]return = 2Friends 1 and 2 swap places between the two days, so they cannot be in the same group. Friend 3 visits after both of them on both days.
So {1, 3} and {2, 3} are consistent groups of size 2, and no group of size 3 works.
Example 2
orders = [[1,4,2,3],[4,1,2,3],[1,2,4,3]]return = 3The group {1, 2, 3} visits in the order 1, 2, 3 on all three days, even though friend 4 sometimes comes between them.
Friend 4 cannot join it: 4 is after 1 on day 0 but before 1 on day 1. So the answer is 3.
Example 3
orders = [[1,2,3],[3,2,1]]return = 1The second day reverses the first, so every two friends switch order. Only groups of one friend are consistent.
Constraints
1 <= n == orders.length <= 51 <= k == orders[d].length <= 10001 <= orders[d][p] <= k- Each row
orders[d]contains every number from1tokexactly once.
More AuxoAI Online Assessment questions
Similar questions at other companies
- Select Transactions with Child-Pays-for-Parent PackagesCoinbase · PHONE SCREENCoinbase interview questions
- Parallel Courses IIIGoogle · ONSITE INTERVIEWGoogle interview questions
- Cheapest Flights Within K StopsGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Planets Queries from Planet OneAdyen · PHONE SCREENAdyen interview questions
- Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
- Delete K Subsets for Maximum ScoreRubrik · OARubrik interview questions
- Optimize Discount Selection Under a Point BudgetPalantir · OAPalantir interview questions
- Maximum Index-Weighted Sum with Disjoint SwapsVisa · OAVisa interview questions
- Recoverable Elements from Range-Sum MeasurementsEthos Life · OA
- Maximum Sum of HeightsVirtu Financial · OAVirtu Financial interview questions