Find Slope

Easy
0/40
Average time to solve is 22m
profile
Contributed by
10 upvotes
Asked in companies
Morgan StanleyHSBCJungleworks

Problem statement

Given a linked list, whose nodes represent the coordinates of the cartesian plane. Find the minimum and the maximum slope of simultaneous points of coordinates.

Linked List : P1(X1, Y1) -> P2( X2, Y2) -> P3(X3, Y3).

Here P1(point1) corresponds to coordinates (X1, Y1), similarly P2(point2) corresponds to coordinates (X2, Y2).

Your task is to find the Maximum(Slope(P1, P2), Slope(P2, P3)) and Minimum(Slope(P1, P2), Slope(P2, P3)).

Note : 
You only need to return the starting node for minimum and maximum slope. So if slope(P1, P2) is maximum, just return P1.

In case of more than one possible solution return the first occurring solution.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' representing the number of Test cases.

The first line of each test case contains linked list elements/nodes separated by space and terminated by -1. Each node would consist of 'X' and 'Y' coordinates.
Output Format: 
For each test case, print the Maximum(Slope(P1, P2), Slope(P2, P3)) and Minimum(Slope(P1, P2), Slope(P2, P3)).
Note 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10        
2 <= N <= 10^3
-10^9 <= X <= 10^9
-10^9 <= Y <= 10^9

Where 'N' denotes the length of the linked list and 'X' and 'Y' denote the coordinates of the 'X' and 'Y' axis respectively.

Time Limit: 1 sec
Sample Input 1:
2
1 5 7 9 6 3 -1
3 2 4 3 5 4 6 5 -1
Sample Output 1:
1 5 7 9
3 2 3 2
Explanation For Sample Input1:
Here we have 2 test cases, hence there are 2 linked lists.

Test Case 1: For the first linked list (1,5)->(7,9)->(6,3), the minimum slope is between nodes (1,5) and (7,9) so we print the first node i.e (1, 5) and the maximum slope is between nodes (7,9) and (6,3) so we print the first node i.e (7, 9).

Tese Case 2: For the second linked list (3,2)->(4,3)->(5,4)->(6,5), there are multiple answers, but we only need first occurring nodes. So the first minimum slope is between nodes (3,2) and (4,3) so we print the first node i.e (3, 2) and the first maximum slope is between nodes (3,2) and (4,3) so we print the first node i.e (3, 2).
Sample Input 2:
2
4 3 8 6 2 9 4 18 -1
2 9 4 18 4 3 8 6 -1
Sample Output 2:
8 6 2 9 
4 3 4 18
Hint

Try to recursively traverse on each node and calculate the slope between consecutive nodes.

Approaches (2)
Recursive Solution
  1. Initially maintain two variables, one for minimum slope and one for maximum slope.
  2. Also, create variables to store coordinates corresponding to the minimum and maximum slope.
  3. Set minimum slope variable value to maximum integer value and maximum slope variable to minimum integer value possible.
  4. Now, traverse recursively through each pair of consecutive nodes using a helper function.
  5. Set the base condition as when ‘node->next’ is NULL.
  6. Calculate the slope between them and store it into a temporary variable.
  7. Slope would be ‘(node2.y - node1.y)/(node2.x - node1.x)’ ,where ‘node2’ and ‘node1’ are two consecutive pair of nodes in linked list.
  8. Now compare the temporary variable with the minimum and maximum variables.
  9. If the temporary variable is less than the minimum variable, set the minimum variable to the temporary variable and replace the coordinates corresponding to the minimum slope with that node.
  10. Also if the temporary variable is greater than the maximum variable, set the maximum variable to the temporary variable and replace the coordinates corresponding to the maximum slope with that node.
  11. Now recursively call for the next node.
  12. Return the minimum slope coordinates and the maximum slope coordinates.
Time Complexity

O(N), where N is the size of the Linked List.

 

We are recursively traversing through the linked list of size N, for N nodes time complexity will be O(N).

Space Complexity

O(N), where N is the size of the Linked List.

 

As we are recursively traversing the linked list, stack space for recursive calls of N nodes of the linked list will be in the order of N. Hence the space complexity will be O(N). 

Code Solution
(100% EXP penalty)
Find Slope
Full screen
Console