### Darkcodefreak's blog

By Darkcodefreak, 9 months ago,

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.

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}

Example 3:

N = 5

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

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

• -2

 » 3 months ago, # |   0 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;iarr[maxIndex]) maxIndex = i; } ans[maxIndex] = 0; // right greater element Stack 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;iarr[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, # ^ |   0 only passes the sample cases
•  » » » 6 days ago, # ^ |   0 Really
•  » » 3 days ago, # ^ |   0 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 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, # |   0 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.