HackerRank Extremum Permutations Problem Solution

HackerRank Extremum Permutations Solution

Yashwant Parihar,

In this post, we will solve HackerRank Extremum Permutations Problem Solution.

Let’s consider a permutation P = {p1, p2, …, pN} of the set of N = {1, 2, 3, …, N} elements .

P is called a magic set if it satisfies both of the following constraints:

  • Given a set of K integers, the elements in positions a1, a2, …, aK are less than their adjacent elements, i.e., pai-1 > pai < pai+1
  • Given a set of L integers, elements in positions b1, b2, …, bL are greater than their adjacent elements, i.e., pbi-1 < pbi > pbi+1

How many such magic sets are there?

Input Format
The first line of input contains three integers N, K, L separated by a single space.
The second line contains K integers, a1, a2, … aK each separated by single space.
the third line contains L integers, b1, b2, … bL each separated by single space.

Output Format
Output the answer modulo 1000000007 (109+7).

Constraints
3 <= N <= 5000
1 <= K, L <= 5000
2 <= ai, bj <= N-1, where i ∈ [1, K] AND j ∈ [1, L]

Sample Input #00

4 1 1
2
3

Sample Output #00

5

Explanation #00

Here, N = 4 a1 = 2 and b1 = 3. The 5 permutations of {1,2,3,4} that satisfy the condition are

  • 2 1 4 3
  • 3 2 4 1
  • 4 2 3 1
  • 3 1 4 2
  • 4 1 3 2

Sample Input #01

10 2 2
2 4
3 9

Sample Output #01

161280
HackerRank Extremum Permutations Problem Solution
HackerRank Extremum Permutations Problem Solution

Extremum Permutations C Solution

#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
int o[5000]={0};
long long dp[5000][5000]={0};

int main(){
  int N,K,L,x,i,j;
  long long sum;
  scanf("%d%d%d",&N,&K,&L);
  for(i=0;i<K;i++){
    scanf("%d",&x);
    if(o[x-1]==1){
      printf("0");
      exit(0);
    }
    o[x-1]=-1;
    if(o[x]==-1){
      printf("0");
      exit(0);
    }
    o[x]=1;
  }
  for(i=0;i<L;i++){
    scanf("%d",&x);
    if(o[x-1]==-1){
      printf("0");
      exit(0);
    }
    o[x-1]=1;
    if(o[x]==1){
      printf("0");
      exit(0);
    }
    o[x]=-1;
  }
  dp[0][0]=1;
  for(i=1;i<N;i++){
    sum=0;
    switch(o[i]){
      case 0:
        for(j=0,sum=0;j<i;j++)
          sum=(sum+dp[i-1][j])%MOD;
        for(j=0;j<=i;j++)
          dp[i][j]=sum;
        break;
      case -1:
        for(j=i-1,sum=0;j>=0;j--){
          sum=(sum+dp[i-1][j])%MOD;
          dp[i][j]=sum;
        }
        break;
      default:
        for(j=0,sum=0;j<i;j++){
          sum=(sum+dp[i-1][j])%MOD;
          dp[i][j+1]=sum;
        }
    }
  }
  for(i=0,sum=0;i<N;i++)
    sum=(sum+dp[N-1][i])%MOD;
  printf("%lld",sum);
  return 0;
}

Extremum Permutations C++ Solution

#include <bits/stdc++.h>

using namespace std;

#define ULL unsigned long long
#define LF __float128

#define MOD 1000000007

int main() {
    int N, K, L;
    cin >> N >> K >> L;

    vector<bool> LMin(N + 1, false);
    vector<bool> LMax(N + 1, false);

    for (int i = 0; i < K; i++) {
        int A;
        cin >> A;

        LMin[A] = true;
        LMax[A + 1] = true;
    }

    for (int i = 0; i < L; i++) {
        int A;
        cin >> A;

        LMax[A] = true;
        LMin[A + 1] = true;
    }

    vector<vector<ULL>> DP(N + 1, vector<ULL>(N + 1, 0));

    DP[1][1] = 1;
    for (int i = 2; i <= N; i++) {
        if (LMin[i] && LMax[i]) {
            cout << 0;
            return 0;
        }

        if (LMin[i]) {
            ULL S = 0;
            for (int j = i; j >= 1; j--) {
                DP[i][j] = S;
                S = (S + DP[i - 1][j - 1]) % MOD;
            }
        } else if (LMax[i]) {
            ULL S = 0;
            for (int j = 1; j <= i; j++) {
                DP[i][j] = S;
                S = (S + DP[i - 1][j]) % MOD;
            }
        } else {
            ULL S = 0;
            for (int j = 1; j <= i; j++) {
                S = (S + DP[i - 1][j]) % MOD;
            }
            for (int j = 1; j <= i; j++) {
                DP[i][j] = S;
            }
        }
    }

    ULL ans = 0;
    for (int i = 1; i <= N; i++) {
        ans = (ans + DP[N][i]) % MOD;
    }
//
//    for (int i = 1; i <= N; i++) {
//        cout << LMin[i] << " " << LMax[i] << endl;
//    }
//    cout << endl;
//
//    for (int i = 1; i <= N; i++) {
//        for (int j = 1; j <= N; j++) {
//            cout << DP[i][j] << " ";
//        }
//        cout << endl;
//    }

    cout << ans;

    return 0;
}

Extremum Permutations C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{
    private enum ExtremumType {
        Peak,
        Valley
    }

    private class Extremum {
        public int Index { get; init; }
        public ExtremumType Type { get; init; }
    }

    private const long m = 1000000007;

    /*
     * Complete the 'extremumPermutations' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. INTEGER_ARRAY a
     *  3. INTEGER_ARRAY b
     */

    public static int extremumPermutations(int n, int[] peaks, int[] valleys)
    {
    checked {
        peaks = peaks.Distinct().ToArray();
        valleys = valleys.Distinct().ToArray();

        if (peaks.Intersect(valleys).Any()) {
            return 0;
        }

        Array.Sort(peaks);
        Array.Sort(valleys);

        for (var i = 1; i < peaks.Length; ++i) {
            if (peaks[i] == peaks[i - 1] + 1) {
                return 0;
            }
        }

        for (var i = 1; i < valleys.Length; ++i) {
            if (valleys[i] == valleys[i - 1] + 1) {
                return 0;
            }
        }

        var peakExtremums =
            peaks.Select(p => new Extremum { Index = p, Type = ExtremumType.Peak });
        var valleyExtremums =
            valleys.Select(v => new Extremum { Index = v, Type = ExtremumType.Valley });
        var extremums = peakExtremums.Concat(valleyExtremums).OrderBy(e => e.Index).ToArray();

        var ctr = 1L;
        var setSize = n;
        var dpPrev = new long[n];
        var dpCur = new long[n];
        
        if (extremums.Length > 0) {
            if (extremums[0].Type == ExtremumType.Peak) {
                dpPrev[0] = setSize - 1;

                for (var i = 1; i < setSize - 2; ++i) {
                    dpPrev[i] = dpPrev[i - 1] + (setSize - i - 1);
                }
            } else {
                dpPrev[setSize - 3] = setSize - 1;

                for (var i = setSize - 4; i >= 0; --i) {
                    dpPrev[i] = dpPrev[i + 1] + (i + 2);
                }
            }

            setSize -= 3;
        }

        for (var i = 1; i < extremums.Length; ++i) {
            if (extremums[i].Index == extremums[i - 1].Index + 2) {
                if (extremums[i].Type == ExtremumType.Peak) {
                    dpCur[setSize - 2] = (dpPrev[setSize - 1] + dpPrev[setSize]) % m;

                    for (var j = setSize - 3; j >= 0; --j) {
                        dpCur[j] = (dpCur[j + 1] + dpPrev[j + 1]) % m;
                    }

                    for (var j = 1; j < setSize - 1; ++j) {
                        dpCur[j] = (dpCur[j] + dpCur[j - 1]) % m;
                    }
                } else {
                    dpCur[0] = (dpPrev[0] + dpPrev[1]) % m;

                    for (var j = 1; j < setSize - 1; ++j) {
                        dpCur[j] = (dpCur[j - 1] + dpPrev[j + 1]) % m;
                    }

                    for (var j = setSize - 3; j >= 0; --j) {
                        dpCur[j] = (dpCur[j] + dpCur[j + 1]) % m;
                    }
                }

                (dpCur, dpPrev) = (dpPrev, dpCur);
                setSize -= 2;
            } else if (extremums[i].Index == extremums[i - 1].Index + 1) {
                if (extremums[i].Type == ExtremumType.Peak) {
                    dpCur[0] = dpPrev[0];

                    for (var j = 1; j < setSize; ++j) {
                        dpCur[j] = (dpCur[j - 1] + dpPrev[j]) % m;
                    }
                } else {
                    dpCur[setSize - 1] = dpPrev[setSize];

                    for (var j = setSize - 2; j >= 0; --j) {
                        dpCur[j] = (dpCur[j + 1] + dpPrev[j + 1]) % m;
                    }
                }

                (dpCur, dpPrev) = (dpPrev, dpCur);
                --setSize;
            } else {
                ctr = (ctr * (dpPrev.Take(setSize + 1).Sum() % m)) % m;

                if (extremums[i].Type == ExtremumType.Peak) {
                    dpPrev[0] = setSize - 1;

                    for (var j = 1; j < setSize - 2; ++j) {
                        dpPrev[j] = dpPrev[j - 1] + (setSize - j - 1);
                    }
                } else {
                    dpPrev[setSize - 3] = setSize - 1;

                    for (var j = setSize - 4; j >= 0; --j) {
                        dpPrev[j] = dpPrev[j + 1] + (j + 2);
                    }
                }

                setSize -= 3;
            }
        }

        ctr = (ctr * (dpPrev.Take(setSize + 1).Sum() % m)) % m;
        ctr = (ctr * Factorial(setSize)) % m;

        return (int)ctr;
    }
    }

    private static long Factorial(int n) {
    checked {
        var result = 1L;

        for (var i = n; i > 1; --i) {
            result = (result * i) % m;
        }

        return result;
    }
    }
}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');

        int n = Convert.ToInt32(firstMultipleInput[0]);

        int k = Convert.ToInt32(firstMultipleInput[1]);

        int l = Convert.ToInt32(firstMultipleInput[2]);

        var a = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(aTemp => Convert.ToInt32(aTemp) - 1).ToArray();

        var b = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(bTemp => Convert.ToInt32(bTemp) - 1).ToArray();

        int result = Result.extremumPermutations(n, b, a);

        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

Extremum Permutations Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'extremumPermutations' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. INTEGER_ARRAY a
     *  3. INTEGER_ARRAY b
     */

    public static int extremumPermutations(int n, List<Integer> A, List<Integer> B) {
        int k = A.size();
        int l = B.size();
        int[] a = new int[5005];
        int[] b = new int[5005];
        long[][] dp = new long[5005][5005];
        
        for (int i = 0; i < k; i++) {
            a[A.get(i)] = 1;
        }

        for (int i = 0; i < l; i++) {
            b[B.get(i)] = 1;
        }

        for (int i = 1; i < n; i++) {
            if (a[i] == 1 && b[i] == 1){
                //System.out.println(0);
                return 0;
            }
            if ((a[i-1] == 1 && a[i] == 1) || (b[i-1]==1 && b[i] == 1)){
                //System.out.println(0);
                return 0;
            }
        }

        dp[1][1] = 1;
        for (int i = 2; i <= n; i++){
            if (!(a[i-1] == 1  || b[i] == 1)){
                long sum = 0;
                for (int j=1; j <= i; j++){
                    dp[i][j] = add(dp[i][j], sum);
                    sum = add(sum, dp[i-1][j]);
                }
            }
            if (!(b[i-1] == 1 || a[i] == 1)){
                long sum = 0;
                for (int j=i; j>=1; j--){
                    dp[i][j] = add(dp[i][j], sum);
                    sum = add(sum, dp[i-1][j-1]);
                }
            }
        }

        long ans = 0;
        for (int i = 1; i <= n; i++){
            ans = add(ans, dp[n][i]);
        }

        return (int) ans;

    }

    private static long add(long x, long v){
        return (x+v) % 1000000007;
    }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

        int n = Integer.parseInt(firstMultipleInput[0]);

        int k = Integer.parseInt(firstMultipleInput[1]);

        int l = Integer.parseInt(firstMultipleInput[2]);

        List<Integer> a = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        List<Integer> b = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        int result = Result.extremumPermutations(n, a, b);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Extremum Permutations JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

function extremumPermutations(n, a, b) {
    var k = a.length, l = b.length;
    var greater = new Array(n).fill(false), less = new Array(n).fill(false);
    var i, j;
    for (i = 0; i < k; i++) {
        less[a[i] - 1] = true;
        greater[a[i]] = true;
    }
    for (i = 0; i < l; i++) {
        greater[b[i] - 1] = true;
        less[b[i]] = true;
    }
    var dp = Array.from(Array(n), () => new Array(n).fill(0));
    dp[0][0] = 1;
    for (i = 1; i < n; i++) {
        var suml = 0, sumr = 0;
        if (!less[i])
            for (j = 1; j <= i; j++) {
                suml += dp[i - 1][j - 1];
                dp[i][j] += suml % 1000000007;
            }
        if (!greater[i])
            for (j = i - 1; j >= 0; j--) {
                sumr += dp[i - 1][j];
                dp[i][j] += sumr % 1000000007;
            }
    }
    var result = dp[n - 1].reduce((a, b) => a + b);
    return (result % 1000000007);
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const nkl = readLine().split(' ');

    var n = parseInt(nkl[0], 10);

    var k = parseInt(nkl[1], 10);

    var l = parseInt(nkl[2], 10);
    
    const a = readLine().split(' ').map(aTemp => parseInt(aTemp, 10));

    const b = readLine().split(' ').map(bTemp => parseInt(bTemp, 10));

    let result = extremumPermutations(n, a, b);

    ws.write(result + "\n");

    ws.end();
}

Extremum Permutations Python Solution

import sys

N, K, L = map(int,input().split())
mins = list(map(int, input().split()))
maxs = list(map(int, input().split()))

M = int(1e9 + 7)
ANY = 0
UP = 1
DOWN = -1
direction = [0] * (N + 1)

for i in mins:
    if direction[i - 1] == UP or direction[i] == DOWN:
        print("0")
        sys.exit(0)
    direction[i - 1] = DOWN
    direction[i] = UP
for i in maxs:
    if direction[i - 1] == DOWN or direction[i] == UP:
        print("0")
        sys.exit(0)
    direction[i - 1] = UP
    direction[i] = DOWN
f = []
for i in range(N + 1):
    f.append([0] * (N + 1))

def interval(a, b):
    if a <= b:
        return range(a, b + 1)
    else:
        return range(a, b - 1, -1)

f[N][0] = 1
i = N - 1
while i > 0:
    if direction[i] == UP:
        f[i][0] = 0
        for n in interval(1, N - i):
            f[i][n] = (f[i][n - 1] + f[i + 1][n - 1]) % M       
    elif direction[i] == DOWN:
        f[i][N - i] = 0
        for n in interval(N - i - 1, 0):
            m = N - i - n
            f[i][n] = (f[i][n + 1] + f[i + 1][n]) % M  
    elif direction[i] == ANY:
        s = 0
        for k in interval(0, N - (i + 1)):
            s += f[i + 1][k]
            s %= M
        for n in interval(0, N - i):
            f[i][n] = s
    i -= 1

ret = 0
for k in interval(0, N - 1):
    ret += f[1][k]
    ret %= M
print(ret)
c C# C++ HackerRank Solutions java javascript python