How should I practice Aladdin and the Magic Carpet?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Fivetran phone screen problems in FastPrep.

Is Aladdin and the Magic Carpet associated with Fivetran?

FastPrep tags this as a Fivetran phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Aladdin and the Magic Carpet

Learn this problem

● Medium

FivetranFULLTIMEPHONE SCREEN

Problem statement

Aladdin wants to travel once around a circular route containing n magic sources numbered from 0 to n - 1.

You are given two integer arrays of equal length:

magic[i] is the amount of magic collected at source i.
dist[i] is the amount of magic required to travel from source i to source (i + 1) % n.

Aladdin may begin at any source with zero magic. At each source, he collects its magic before paying the travel cost to the next source. His remaining magic may never become negative.

Return the smallest zero-based starting index from which Aladdin can complete exactly one full circuit. If no starting index works, return -1.

Function

optimalPoint(magic: int[], dist: int[]) → int

Examples

Example 1

magic = [1,5,3,2]dist = [2,2,4,2]return = 1

Starting at source 0 fails immediately because collecting 1 magic cannot pay a cost of 2.

Starting at source 1, the remaining magic after each trip is 3, 2, 2, and 1. The full circuit succeeds, so the smallest feasible index is 1.

Example 2

magic = [2,1,1]dist = [3,2,2]return = -1

The route provides 4 units of magic but requires 7 units in total. No starting point can complete the circuit.

Example 3

magic = [2,2]dist = [1,1]return = 0

Either source can begin a successful circuit. The required result is the smaller feasible index, 0.

Constraints

1 <= magic.length == dist.length <= 100000.
0 <= magic[i] <= 10000.
0 <= dist[i] <= 10000.