-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree
/
Copy pathPairs.java
More file actions
179 lines (147 loc) · 4.28 KB
/
Pairs.java
File metadata and controls
179 lines (147 loc) · 4.28 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
package hackerrank;
import java.util.Arrays;
/**
* Problem:
* https://www.hackerrank.com/challenges/pairs/problem
*
* You will be given an array of integers and a target value.
* Determine the number of pairs of array elements that have
* a difference equal to a target value.
*
* Function Description:
* Complete the pairs function below. It must return an integer
* representing the number of element pairs having the required
* difference.
*
*/
public class Pairs {
public static void main(String[] args) {
validSwapCountEquals5();
validSwapCountEquals3();
}
public static void validSwapCountEquals5() {
int[] arr = {1, 2, 3, 4, 5, 6, 8}; //1,3; 2,4; 3,5; 4,6, 6,8
int k = 2;
int result = pairs(k, arr);
int expected = 5;
assert (result == expected) : "Result:" + result +" | Expected:" + expected;
}
public static void validSwapCountEquals3() {
int[] arr = {1, 5, 3, 4, 2};
int k = 2;
int result = pairs(k, arr);
int expected = 3;
assert (result == expected) : "Result:" + result +" | Expected:" + expected;
}
/**
* This is the solution tha passed time constraints in hackerrank.
* It uses two pointers scanning from front.
*
* T = O(N)
*
* @param k
* @param arr
* @return
*/
public static int pairs(int k, int[] arr) {
Arrays.sort(arr);
int arrLen = arr.length;
int i=0;
int j=1;
int count=0;
while( j < arrLen ) {
int diff = arr[j] - arr[i];
if (diff == k) {
count++;
j++;
} else if (diff > k) {
i++;
} else if (diff < k) {
j++;
}
}
return count;
}
/**
* The solution is not optimum and fails due to time out.
* T = O(N^2)
*
* @param k
* @param arr
* @return
*/
public static int pairsONSquare(int k, int[] arr) {
Arrays.sort(arr);
// first forloop to loop over all
// second forloop to check for pair
int arrLen = arr.length;
int pairCount = 0;
for ( int i = 0; i < arrLen; i++ ) {
for (int j = i+1; j < arrLen; j++ ) {
int sum = arr[j] - arr[i];
if ( sum == k ) pairCount++;
}
}
return pairCount;
}
/**
* This solution does not work.
*
* This was the first thought process for the solution with 4 pointers.
* The idea basically was to explore the array from both ways, i.e.
* from the front and as well as the back. This got complicated but
* I believe the solution is near to be found if more time given.
*
* @param k
* @param arr
* @return
*/
public static int pairsX(int k, int[] arr) {
Arrays.sort(arr);
int arrLen = arr.length - 1;
int arrBack = arrLen;
int arrFront = 0;
int pairsCount = 0;
int fi = 1;
int bj = arrBack - 1;
//fi != arrFront && bj != arrBack
while ( arrBack > arrFront ) {
if ( bj < 0 ) {
arrBack--;
bj = arrBack - 1;
}
if ( fi > arrLen + 1 ) {
arrFront++;
fi = arrFront + 1;
}
int frontSum = arr[fi] - arr[arrFront];
if ( frontSum > k ) {
arrFront++;
fi = arrFront + 1;
} else if ( frontSum == 2 ) {
pairsCount++;
if ( arr[arrFront] == arr[arrFront + 1] ) {
arrFront = arrFront + 2;
pairsCount++;
}
fi++;
} else {
fi++;
}
int backSum = arr[arrBack] - arr[bj];
if ( backSum > k ) {
arrBack--;
bj = arrBack - 1;
} else if ( backSum == 2 && fi < arrBack ) {
if ( arr[arrBack] == arr[arrBack - 1] ) {
arrBack = arrBack - 2;
pairsCount++;
}
pairsCount++;
} else {
bj--;
}
}
return pairsCount;
}
}