Número de edificios estrictamente crecientes desde la derecha con colores distintos

Dado un número entero  y dos conjuntos de números enteros H[] y C[] de tamaño  donde H[] almacena la altura de edificios consecutivos y C[] almacena los códigos de color para aquellos edificios en los que están pintados. 
La tarea es determinar cuántos colores son visibles a la vez desde la vista de la derecha, es decir, a la derecha del edificio más a la derecha.
Ejemplos: 
 

Entrada: K = 5, H[] = {5, 4, 3, 2, 3}, C[] = {1, 2, 3, 4, 5} 
Salida: 3 
 

Entrada: K = 5, H[] = {1, 2, 3, 4, 5}, C[] = {3, 3, 3, 3, 3} 
Salida: 1 
 

Enfoque: al observar detenidamente, el problema anterior se puede simplificar para encontrar el número de edificios estrictamente crecientes desde la derecha con colores distintos. 
 

1. Almacene el último elemento de la array Height en la variable max .
2. Ahora en una array Arr , en la posición correspondiente al elemento en el último almacén de la array de colores 1 .
3. Ahora comience a recorrer la array Height de n-2 a 0 .
4. Si obtenemos un elemento mayor que max , almacene esa variable en max y nuevamente en la array Arr , en la posición correspondiente al i-ésimo elemento en la array de color store 1 . 
    
5. Por último, cuente el número de 1 presentes en la array Arr . Da el número total de color visible desde el final.

A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation of above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number of
// colors visible
int colourVisible(int height[], int colour[], int K)
{
    int arr[K + 1] = { 0 }, visible = 0;
 
    int max = height[K - 1];
    arr[colour[K - 1]] = 1;
 
    for (int i = K - 2; i >= 0; i--) {
        if (height[i] > max) {
            max = height[i];
            arr[colour[i]] = 1;
        }
    }
 
    // Count the Number of 1's
    for (int i = 1; i <= K; i++) {
        if (arr[i] == 1)
            visible++;
    }
 
    return visible;
}
 
// Driver code
int main()
{
    int height[] = { 3, 5, 1, 2, 3 };
    int colour[] = { 1, 2, 3, 4, 3 };
    int K = sizeof(colour) / sizeof(colour[0]);
 
    cout << colourVisible(height, colour, K);
 
    return 0;
}

//Java  implementation of above approach
 
import java.io.*;
 
class GFG {
    // Function to return the number of
// colors visible
static int colourVisible(int height[], int colour[], int K)
{
    int arr[]=new int[K + 1] ;
    int visible = 0;
 
    int max = height[K - 1];
    arr[colour[K - 1]] = 1;
 
    for (int i = K - 2; i >= 0; i--) {
        if (height[i] > max) {
            max = height[i];
            arr[colour[i]] = 1;
        }
    }
 
    // Count the Number of 1's
    for (int i = 1; i <= K; i++) {
        if (arr[i] == 1)
            visible++;
    }
 
    return visible;
}
 
// Driver code
     
    public static void main (String[] args) {
     
    int height[] = { 3, 5, 1, 2, 3 };
    int colour[] = { 1, 2, 3, 4, 3 };
    int K = colour.length;
 
    System.out.println (colourVisible(height, colour, K));
    }
}

# Python3 implementation of above approach
 
# Function to return the number of
# colors visible
def colourVisible(height, colour, K):
    arr = [0 for i in range(K + 1)]
    visible = 0
 
    max = height[K - 1]
    arr[colour[K - 1]] = 1
     
    i = K - 2
    while(i >= 0):
        if (height[i] > max):
            max = height[i]
            arr[colour[i]] = 1
        i -= 1
     
    # Count the Number of 1 complement
    for i in range(1, K + 1, 1):
            if (arr[i] == 1):
                visible += 1
     
    return visible
 
# Driver code
if __name__ == '__main__':
    height = [3, 5, 1, 2, 3]
    colour = [1, 2, 3, 4, 3]
    K = len(colour)
 
    print(colourVisible(height, colour, K))
 
# This code is contributed by
# Surendra_Gangwar

// C# implementation of above approach
using System;
 
class GFG
{
// Function to return the number of
// colors visible
static int colourVisible(int []height,
                         int []colour, int K)
{
    int []arr=new int[K + 1] ;
    int visible = 0;
 
    int max = height[K - 1];
    arr[colour[K - 1]] = 1;
 
    for (int i = K - 2; i >= 0; i--)
    {
        if (height[i] > max)
        {
            max = height[i];
            arr[colour[i]] = 1;
        }
    }
 
    // Count the Number of 1's
    for (int i = 1; i <= K; i++)
    {
        if (arr[i] == 1)
            visible++;
    }
 
    return visible;
}
 
// Driver code
static public void Main ()
{
    int []height = { 3, 5, 1, 2, 3 };
    int []colour = { 1, 2, 3, 4, 3 };
    int K = colour.Length;
     
    Console.WriteLine(colourVisible(height, colour, K));
}
}
 
// This code is contributed by Sach_Code

<?php
// PHP implementation of above approach
 
// Function to return the number of
// colors visible
function colourVisible($height, $colour, $K)
{
    $arr = array_fill(0, $K + 1, 0);
    $visible = 0;
 
    $max = $height[$K - 1];
    $arr[$colour[$K - 1]] = 1;
 
    for ($i = $K - 2; $i >= 0; $i--)
    {
        if ($height[$i] > $max)
        {
            $max = $height[$i];
            $arr[$colour[$i]] = 1;
        }
    }
 
    // Count the Number of 1's
    for ($i = 1; $i <= $K; $i++)
    {
        if ($arr[$i] == 1)
            $visible++;
    }
 
    return $visible;
}
 
// Driver code
$height = array( 3, 5, 1, 2, 3 );
$colour = array( 1, 2, 3, 4, 3 );
$K = count($colour);
 
echo colourVisible($height, $colour, $K);
 
// This code is contributed by mits
?>

<script>
 
// Javascript implementation of above approach
 
// Function to return the number of
// colors visible
function colourVisible(height, colour, K)
{
    var arr = Array(K+1).fill(0), visible = 0;
 
    var max = height[K - 1];
    arr[colour[K - 1]] = 1;
 
    for (var i = K - 2; i >= 0; i--) {
        if (height[i] > max) {
            max = height[i];
            arr[colour[i]] = 1;
        }
    }
 
    // Count the Number of 1's
    for (var i = 1; i <= K; i++) {
        if (arr[i] == 1)
            visible++;
    }
 
    return visible;
}
 
// Driver code
var height = [ 3, 5, 1, 2, 3 ];
var colour = [ 1, 2, 3, 4, 3 ];
var K = colour.length;
document.write( colourVisible(height, colour, K));
 
</script>

2

Complejidad de tiempo: O(K), donde K es el tamaño de la array de colores
Espacio auxiliar: O(K), ya que se usa un tamaño adicional de K