Darkcodefreak's blog

By Darkcodefreak, 9 months ago, In English

There are N platforms in a row each having unique height. The height of N platforms is given in the form of an array A.

You can perform the following operation

If one is standing on the ith platform, you can jump to the jth platform if and only if the height of the ith platform is greater than the jth platform and there is no platform between the ith and jth platform whose height is greater than the jth platform.

You are standing on the highest platform in the array. Find the minimum number of jumps required to reach each of the platforms present in the given array.

Follow 1-based indexing

Example 1:

N = 4

A = {1, 3, 6, 5}

Platform 3 is having the maximum height so starting position is 3 and A[3] = 6

Answer = {2, 1, 0, 1}

1st platform: 3 -> 2 -> 1

2nd platform: 3 -> 2

3rd platform: 3 (Starting position)

4th platform: 3 -> 4

Example 2:

N = 2

A = {3, 5}

Answer = {1, 0}

Example 3:

N = 5

A = {5, 1, 3, 4, 7}

Answer = {1, 2, 2, 1, 0}

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do Next Greater element from right once and Do next greater element from left once.

import java.util.*;

public class Main {
    public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int arr[]=new int[n];
      int ans[]=new int[n];
      int maxIndex = 0;
      for(int i=0;i<n;i++){
        arr[i]=sc.nextInt();
        ans[i]= Integer.MAX_VALUE;
        if(arr[i]>arr[maxIndex])
        maxIndex = i;
      }
      ans[maxIndex] = 0;
      // right greater element
      Stack<Integer> st = new Stack<>();
      st.add(maxIndex);
      for(int i=maxIndex-1;i>=0;i--){
        
          while(arr[i]>arr[st.peek()])
          st.pop();
          ans[i] = ans[st.peek()]+1;
          st.add(i);
      }
      
      
      // left greater element
      
      st.clear();
      st.add(0);
      for(int i=1;i<n;i++){
        while(!st.isEmpty() && arr[i]>arr[st.peek()])
            st.pop();
        if(!st.isEmpty())
        ans[i]= Math.min(ans[i],ans[st.peek()]+1);
        st.add(i);
      }
      System.out.println();
      for(int i:ans)
      System.out.print(i+" ");
      
      
    }
}
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    only passes the sample cases

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    static int[] Min_Jumps(int N, int[] A) { ArrayList nodeList = createNodeList(A); assignChildNodes(nodeList);

    // Optional print of created Node Structure
    // printNodeStructure(nodeList);
    
    int[] result = new int[N];
    Node startNode = nodeList.get(Tallest(A));
    
    // Get number of jumps to reach each platform
    for (int platform = 0; platform < nodeList.size(); platform++) {
        Node destination = nodeList.get(platform);
        for (int jumps = 0; jumps < nodeList.size(); jumps++) {
            HashSet<Node> nextReachableNodes = reachableNodesFromNodeWithJumps(startNode, jumps);
            if (nextReachableNodes.contains(destination)) {
                result[platform] = jumps;
                break;
            }
        }
    }
    
    // Print results
    for (int e : result) {
        System.out.println(e);
    }
    return result;

    }

    static ArrayList createNodeList(int[] arr) { ArrayList nodeList = new ArrayList<>(); for (int e : arr) { nodeList.add(new Node(e)); } return nodeList; }

    static void assignChildNodes(ArrayList nodeList) { for (int outerNodeIndex = 0; outerNodeIndex < nodeList.size(); outerNodeIndex++) { Node outerNode = nodeList.get(outerNodeIndex); for (int innerNodeIndex = 0; innerNodeIndex < nodeList.size(); innerNodeIndex++) { Node innerNode = nodeList.get(innerNodeIndex); if (outerNode.value > innerNode.value) { List sublist; if (outerNodeIndex < innerNodeIndex) { sublist = nodeList.subList(outerNodeIndex + 1, innerNodeIndex); } else { sublist = nodeList.subList(innerNodeIndex + 1, outerNodeIndex); } if (sublist.size() == 0) { outerNode.childNodes.add(innerNode); } else { loop: { for (Node element : sublist) { if (element.value > innerNode.value) { break loop; } } outerNode.childNodes.add(innerNode); } } } } } }

    static HashSet reachableNodesFromNodeWithJumps(Node node, int jumps) { HashSet nextReachableNodes = new HashSet<>(); nextReachableNodes.add(node); while (jumps > 0) { ArrayList nextNodes = new ArrayList<>(); nextReachableNodes.forEach(n -> nextNodes.addAll(n.childNodes)); nextReachableNodes.addAll(nextNodes); jumps -= 1; } return nextReachableNodes; }

    static void printNodeStructure(ArrayList nodes) { for (Node node : nodes) { System.out.println(node.toString()); System.out.println("Childs:"); node.childNodes.forEach(childNode -> System.out.println(childNode.toString())); System.out.println("-------------"); } }

    //Function to find the index of max number in array static int Tallest(int[] arr) { //since have to use 1based indexing int max = 0;

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > arr[max]) {
            max = i;
        }
    }
    return max;

    }

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Store index of each element, then starting from the maximal element, using BFS you can go to the next smallest element and minimize the answer for the adjacent elements.