Skip to content

Commit 30597d5

Browse files
varunu28varunu28
committed
Added 1 solution & refactored 3 solutions
1 parent e529f20 commit 30597d5

4 files changed

+101
-93
lines changed

‎Easy/Two Sum Less Than K.java

Lines changed: 13 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,17 @@
11
class Solution {
2-
public int twoSumLessThanK(int[] A, int K) {
3-
TreeSet<Integer> set = new TreeSet<>();
4-
int maxSum = -1;
5-
6-
for (int i = 0; i < A.length; i++) {
7-
int diff = K - A[i];
8-
if (diff > 0) {
9-
Integer second = set.lower(diff);
10-
if (second != null) {
11-
maxSum = Math.max(maxSum, A[i] + second);
12-
}
13-
}
14-
15-
set.add(A[i]);
2+
public int twoSumLessThanK(int[] A, int K) {
3+
int maxSum = -1;
4+
TreeSet<Integer> set = new TreeSet<>();
5+
for (int i = 0; i < A.length; i++) {
6+
int diff = K - A[i];
7+
if (diff > 0) {
8+
Integer half = set.lower(diff);
9+
if (half != null) {
10+
maxSum = Math.max(maxSum, A[i] + half);
1611
}
17-
18-
return maxSum;
12+
}
13+
set.add(A[i]);
1914
}
15+
return maxSum;
16+
}
2017
}

‎Medium/Analyze User Website Visit Pattern.java

Lines changed: 52 additions & 54 deletions
Original file line numberDiff line numberDiff line change
@@ -1,60 +1,58 @@
11
class Solution {
2-
public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
3-
Map<String, List<Visit>> visitMap = new HashMap<>();
4-
int n = username.length;
5-
for (int i = 0; i < n; i++) {
6-
visitMap.computeIfAbsent(username[i], k -> new ArrayList<>()).add(new Visit(timestamp[i], website[i]));
7-
}
8-
9-
Map<String, Integer> tripletMap = new HashMap<>();
10-
for (String user : visitMap.keySet()) {
11-
List<Visit> visits = visitMap.get(user);
12-
Collections.sort(visits);
13-
Set<String> visited = new HashSet<>();
14-
for (int i = 0; i < visits.size(); i++) {
15-
for (int j = i + 1; j < visits.size(); j++) {
16-
for (int k = j + 1; k < visits.size(); k++) {
17-
String tempTriplet = visits.get(i).website + "," + visits.get(j).website + "," + visits.get(k).website;
18-
if (visited.add(tempTriplet)) {
19-
tripletMap.put(tempTriplet, tripletMap.getOrDefault(tempTriplet, 0) + 1);
20-
}
21-
}
22-
}
23-
}
24-
}
25-
26-
int maxValue = 0;
27-
String res = "";
28-
for (String triplet : tripletMap.keySet()) {
29-
if (tripletMap.get(triplet) > maxValue) {
30-
maxValue = tripletMap.get(triplet);
31-
res = triplet;
32-
}
33-
else if (tripletMap.get(triplet) == maxValue) {
34-
if (triplet.compareTo(res) < 0) {
35-
res = triplet;
36-
}
37-
}
38-
}
39-
40-
return Arrays.asList(res.split(","));
2+
public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
3+
List<List<String>> sessions = new ArrayList<>();
4+
int n = timestamp.length;
5+
// Form a session list -> user[i] at timestamp[i] visited website[i]
6+
for (int i = 0; i < n; i++) {
7+
sessions.add(new ArrayList<>());
8+
sessions.get(i).add(username[i]);
9+
sessions.get(i).add(String.valueOf(timestamp[i]));
10+
sessions.get(i).add(website[i]);
4111
}
42-
}
43-
44-
class Visit implements Comparable<Visit> {
45-
int timestamp;
46-
String website;
47-
48-
public Visit(int timestamp, String website) {
49-
this.timestamp = timestamp;
50-
this.website = website;
12+
// Sort by timestamp
13+
sessions.sort((a, b) -> Integer.parseInt(a.get(1)) - Integer.parseInt(b.get(1)));
14+
Map<String, List<String>> visited = new HashMap<>();
15+
// Create a hashmap user -> list of websites visited
16+
for (int i = 0; i < n; i++) {
17+
visited.computeIfAbsent(sessions.get(i).get(0), k -> new ArrayList<>()).add(sessions.get(i).get(2));
5118
}
52-
53-
public String toString() {
54-
return timestamp + "->" + website;
19+
Map<String, Integer> sequence = new HashMap<>();
20+
int maxCount = 0;
21+
String maxSeq = "";
22+
for (String name : visited.keySet()) {
23+
if (visited.get(name).size() >= 3) {
24+
// Form all possible combination of websites visited of size 3
25+
Set<String> subseqences = subseqence(visited.get(name));
26+
for (String seq : subseqences){
27+
sequence.put(seq, sequence.getOrDefault(seq, 0) + 1);
28+
if(sequence.get(seq) > maxCount){
29+
maxCount = sequence.get(seq);
30+
maxSeq = seq;
31+
}
32+
else if (sequence.get(seq) == maxCount && seq.compareTo(maxSeq) < 0) {
33+
maxSeq = seq;
34+
}
35+
}
36+
}
37+
}
38+
String[] strs = maxSeq.split(",");
39+
List<String> res = new ArrayList<>();
40+
for (String s : strs) {
41+
res.add(s);
5542
}
56-
57-
public int compareTo(Visit visit) {
58-
return this.timestamp - visit.timestamp;
43+
return res;
44+
}
45+
46+
private Set<String> subseqence(List<String> list) {
47+
Set<String> set = new HashSet<>();
48+
int n = list.size();
49+
for (int i = 0; i < n - 2; i++) {
50+
for (int j = i + 1; j < n - 1; j++) {
51+
for (int k = j + 1; k < n; k++) {
52+
set.add(list.get(i) + "," + list.get(j) + "," + list.get(k));
53+
}
54+
}
5955
}
56+
return set;
57+
}
6058
}

‎Medium/Letter Tiles Possibilities.java

Lines changed: 19 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,23 @@
11
class Solution {
2-
public int numTilePossibilities(String tiles) {
3-
int[] occCount = new int[26];
4-
for (char c : tiles.toCharArray()) {
5-
occCount[c - 'A']++;
6-
}
7-
8-
return dfsHelper(occCount);
2+
public int numTilePossibilities(String tiles) {
3+
int[] count = new int[26];
4+
for (char c : tiles.toCharArray()) {
5+
count[c - 'A']++;
96
}
10-
11-
private int dfsHelper(int[] occCount) {
12-
int sum = 0;
13-
14-
for (int i = 0; i < 26; i++) {
15-
if (occCount[i] == 0) {
16-
continue;
17-
}
18-
19-
sum++;
20-
occCount[i]--;
21-
sum += dfsHelper(occCount);
22-
occCount[i]++;
23-
}
24-
25-
return sum;
7+
return dfs(count);
8+
}
9+
10+
private int dfs(int[] count) {
11+
int sum = 0;
12+
for (int i = 0; i < 26; i++) {
13+
if (count[i] == 0) {
14+
continue;
15+
}
16+
sum++;
17+
count[i]--;
18+
sum += dfs(count);
19+
count[i]++;
2620
}
21+
return sum;
22+
}
2723
}

‎Medium/Minimum Cost to Connect Sticks.java

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
class Solution {
2+
public int connectSticks(int[] sticks) {
3+
int cost = 0;
4+
PriorityQueue<Integer> pq = new PriorityQueue<>();
5+
for (int stick : sticks) {
6+
pq.add(stick);
7+
}
8+
while (pq.size() > 1) {
9+
int first = pq.poll();
10+
int second = pq.poll();
11+
int joinSum = first + second;
12+
cost += joinSum;
13+
pq.add(joinSum);
14+
}
15+
return cost;
16+
}
17+
}

0 commit comments

Comments
 (0)