package g0301_0400.s0332_reconstruct_itinerary;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.PriorityQueue;

public class Solution {

public List<String> findItinerary(List<List<String>> tickets) {

HashMap<String, PriorityQueue<String>> map = new HashMap<>();

LinkedList<String> ans = new LinkedList<>();

for (int i = 0; i < tickets.size(); i++) {

String src = tickets.get(i).get(0);

String dest = tickets.get(i).get(1);

PriorityQueue<String> pq = map.getOrDefault(src, new PriorityQueue<>());

pq.add(dest);

map.put(src, pq);

}

dfs(map, "JFK", ans);

return ans;

}

private void dfs(Map<String, PriorityQueue<String>> map, String src, LinkedList<String> ans) {

PriorityQueue<String> temp = map.get(src);

while (temp != null && !temp.isEmpty()) {

String nbr = temp.remove();

dfs(map, nbr, ans);

}

ans.addFirst(src);

}

}

332\. Reconstruct Itinerary

Hard

You are given a list of airline `tickets` where <code>tickets[i] = [from_i, to_i]</code> represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from `"JFK"`, thus, the itinerary must begin with `"JFK"`. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

* For example, the itinerary `["JFK", "LGA"]` has a smaller lexical order than `["JFK", "LGB"]`.

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

**Example 1:**

**Input:** tickets = \[\["MUC","LHR"\],\["JFK","MUC"\],\["SFO","SJC"\],\["LHR","SFO"\]\]

**Output:** \["JFK","MUC","LHR","SFO","SJC"\]

**Example 2:**

**Input:** tickets = \[\["JFK","SFO"\],\["JFK","ATL"\],\["SFO","ATL"\],\["ATL","JFK"\],\["ATL","SFO"\]\]

**Output:** \["JFK","ATL","JFK","SFO","ATL","SFO"\]

**Explanation:**

Another possible reconstruction is

["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

**Constraints:**

* `1 <= tickets.length <= 300`

* `tickets[i].length == 2`

* <code>from_i.length == 3</code>

* <code>to_i.length == 3</code>

* <code>from_i</code> and <code>to_i</code> consist of uppercase English letters.

* <code>from_i != to_i</code>

package g0301_0400.s0334_increasing_triplet_subsequence;

public class Solution {

public boolean increasingTriplet(int[] nums) {

int n = nums.length;

int i = 0;

int low = Integer.MAX_VALUE;

int high = Integer.MAX_VALUE;

while (i < n) {

if (low >= nums[i]) {

low = nums[i++];

} else if (high >= nums[i]) {

high = nums[i++];

} else {

return true;

}

}

return false;

}

}

334\. Increasing Triplet Subsequence

Medium

Given an integer array `nums`, return `true` _if there exists a triple of indices_ `(i, j, k)` _such that_ `i < j < k` _and_ `nums[i] < nums[j] < nums[k]`. If no such indices exists, return `false`.

**Example 1:**

**Input:** nums = \[1,2,3,4,5\]

**Output:** true

**Explanation:** Any triplet where i < j < k is valid.

**Example 2:**

**Input:** nums = \[5,4,3,2,1\]

**Output:** false

**Explanation:** No triplet exists.

**Example 3:**

**Input:** nums = \[2,1,5,0,4,6\]

**Output:** true

**Explanation:** The triplet (3, 4, 5) is valid because nums\[3\] == 0 < nums\[4\] == 4 < nums\[5\] == 6.

**Constraints:**

* <code>1 <= nums.length <= 5 * 10⁵</code>

* <code>-2³¹ <= nums[i] <= 2³¹ - 1</code>

**Follow up:** Could you implement a solution that runs in `O(n)` time complexity and `O(1)` space complexity?

package g0301_0400.s0332_reconstruct_itinerary;

import static org.hamcrest.CoreMatchers.equalTo;

import static org.hamcrest.MatcherAssert.assertThat;

import java.util.Arrays;

import java.util.List;

import org.junit.Test;

public class SolutionTest {

@Test

public void findItinerary() {

List<List<String>> input =

Arrays.asList(

Arrays.asList("MUC", "LHR"),

Arrays.asList("JFK", "MUC"),

Arrays.asList("SFO", "SJC"),

Arrays.asList("LHR", "SFO"));

assertThat(

new Solution().findItinerary(input),

equalTo(Arrays.asList("JFK", "MUC", "LHR", "SFO", "SJC")));

}

}

package g0301_0400.s0334_increasing_triplet_subsequence;

import static org.hamcrest.CoreMatchers.equalTo;

import static org.hamcrest.MatcherAssert.assertThat;

import org.junit.Test;

public class SolutionTest {

@Test

public void increasingTriplet() {

assertThat(new Solution().increasingTriplet(new int[] {1, 2, 3, 4, 5}), equalTo(true));

}

}