Prefix Permutation

A non-empty zero-indexed array A consisting of a permutation of integers from 1 to N is given. A permutation of integers from 1 to K is a sequence containing each element from 1 to K once, and only once. A prefix permutation is an index P such that 0 P < N and such that the sequence A[0], A[1], A[P] is a permutation of integers from 1 to P + 1. The goal is to calculate the number of prefix permutations in the array. For example, consider array A such that:

A[0] = 2 
A[1] = 1 
A[2] = 3 
A[3] = 5 
A[4] = 4

There are exactly three prefix permutations: 1, 2 and 4. This is because the following sequences are permutations of integers from 1 to P + 1:

• for P = 1, the sequence A[0], A[1] contains integers 2, 1,

• for P = 2, the sequence A[0], A[1], A[2] contains integers 2, 1, 3,

• for P = 4, the sequence A[0], A[1], A[2], A[3], A[4] contains integers 2, 1, 3, 5, 4.

The index 3 is not a prefix permutation because the sequence A[0], A[1], A[2], A[3], which contains integers 2,1, 3, 5, is not a permutation of integers from 1 to 4. Write a function: class Solution { public int solution(int[] A); }

that, given a non-empty zero-indexed array A consisting of a permutation of integers from 1 to N, returns the number of prefix permutations.

The Idea: What happens when order does not matter and we are always working with unique positive numbers? Then the partial sum will always be unique. In the example above, we obtain the following partial sum.

input:  [2,1,3,5,4]
cumsum: [2,3,6,11,15]

index:  [1,2,3,4,5]
cumsum: [1,3,6,10,15]

---

cumsum: [2,3,6,11,15]
cumsum: [1,3,6,10,15]
matches:   1 2     3

This works because at every point in time, in order to satisfy the condition that we've come across elements 1-i previously, its unique partial sum must be satisfied. And because of the commutative property of addition, it works perfectly with permutations.

Complexity: O(n) time and O(2n) space. This can be easily modified to run in constant space. The code below is more so for proof of concept.

import numpy as np

def perumation_prefix(nums):
    partial_sum = np.cumsum(nums)
    index_sum = np.cumsum(np.arange(1,len(nums) + 1, 1))
    return sum(val1 == val2 for val1, val2 in zip(partial_sum, index_sum))