m3th0d.itbhu
BAN USER@sam Using O(n) space you can definitely find duplicates in an array in O(n) time complexity.
1) create a temp array of same size as input array.
2) Now assume each zero as -1, so for every index i in temp array, store the count of ones and zeroes till that index in original array. (count of ones + (-1*count of zeroes))
3) find two farthest index which has same value. That would be the answer.
Why so, say at index i and j we have same values. --> S[i] == S[j] --> S[i] + count of ones - count of zeroes =S[i](since S[i] == S[j])
--> count of ones = count of zeroes.
Time complexity = O(n), Space complexity = O(n)
1)create interface Area with method getArea(double ... parameters)
2)have concrete implemetations like rectArea, circArea etc which have getArea method implemented accordingly.
3) Have a base class Shape implements Comparable and which has Area as a member field.
4) Have a constructor like Shape(Area requiredArea){ this.Area = requiredArea) and a method getArea(){ return Area.getArea())
5) Have comparable to act on Area.getArea() of Shape class.
6) Since all are type of Shape class, hence they can be stored in collection of type Shape.
def parseword(a_word):
return max([a_word.count(c) for c in a_word.lower()])
what you have done is definitely log(n) solution but it will make integer overflow very easily as x^n will easily cross integer max limit.
It could be safely done in below steps, not crossing integer overflow limit.
using the formula (ab) mod n = ((a mod n)*(b mod n)) mod n
public int getMod(int x, int y, int z){
if(y == 1)
return x%z;
int halfMod = ((getMod(x, y/2, z)%z) * getMod(x, y/2,z))%z;
if (y%2 == 0){
return halfMod;
}else {
return ((halfMod%z)*(x%z))%z;
}
}
It is O(logY) complexity and will never cross integer max limit.
@Yang, I believe the maximum stack depth would be log n in average case, hence total memory used would be 2 * log n , and in case of array it has to be n. Hence on an average case 2 stacks has to be a preferred option.
Its simply maximum single sell profit algorithm,
Steps:
1) maxDiff = 0, currentMinimum = a[0]
2) for i in [0,n-1] do:
curMinimum = min(curMinimum, a[i])
maxDiff = max(maxDiff, a[i] - curMinimum)
3) maxDiff is the answer
Complexity = O(n)
working code:
public int[] getIndexIandJ(int[] integers){
if(integers == null || integers.length == 1){
return integers;
}
int maxDiff = 0;
int curMin = integers[0];
int startIndex = 0;
int endIndex = 0;
int tempStart = 0;
for(int i = 1; i<integers.length; i++){
if(curMin > integers[i]){
curMin = integers[i];
tempStart = i;
}
if (maxDiff < (integers[i] - curMin)){
maxDiff = (integers[i] - curMin);
startIndex = tempStart;
endIndex = i;
}
}
int[] indices = new int[2];
indices[0] = startIndex;
indices[1] = endIndex;
return indices;
}
Time Complexity = O(d lgd), d = number of digits
eg: 4765
Step 1: Scan from right and insert all numbers into priorityqueue(min heap) which are in
increasing order i.e. 5, 6, and 7
Step2: As our pointer is at '7' start de queue and insert elements starting with location of '7' till we get number just greater than 4. As it is min heap, we will get numbers starting from lower most and hence filling them we ensure we are maitaining the shortest possible number.
step 3: as soon as we get a number just greater than 4, place it at location of '4' and place '4' at location where we were while filling the entries starting from '7',
step:4 fill all the entries remaining in the queue from the location where we placed '4'.
Complexity = O(d) for numbers scanning and lg(d) for heapify operation, hence worst is O(d lgd).
code:
public int getNextLargestNumber(int[] numbers){
int lastIndex = numbers.length -1;
PriorityQueue priorityQueue = new PriorityQueue();
while (lastIndex>0 && (numbers[lastIndex-1] >= numbers[lastIndex])){
priorityQueue.add(numbers[lastIndex]);
lastIndex--;
}
priorityQueue.add(numbers[lastIndex]);
if(priorityQueue.size() == numbers.length){
return getInt(numbers);
}
int justGreater = (Integer)priorityQueue.peek();
priorityQueue.remove(priorityQueue.peek());
int start = lastIndex;
while (justGreater < numbers[lastIndex-1]){
numbers[start++] = justGreater;
justGreater = (Integer)priorityQueue.peek();
priorityQueue.remove(priorityQueue.peek());
}
numbers[start++] = numbers[lastIndex-1];
numbers[lastIndex-1] = justGreater;
while (!priorityQueue.isEmpty()){
numbers[start++] = (Integer)priorityQueue.peek();
priorityQueue.remove(priorityQueue.peek());
}
return getInt(numbers);
}
private int getInt(int[] nums){
int number = 0;
for (int i=0; i<nums.length; i++){
number = number*10 + nums[i];
}
return number;
}
Complexity: O(N^2)
Steps:
1) Pick the first number and try to find two maximum numbers to its right in increasing order,
2) if Found , store the product of all three numbers
3) do this for all numbers
well it can be improved furthure , once we got a triplet a1<a2<a3, we can skip these test for any b right of a1 and left of a2 where b<a1.
public int getMaxProd(int[] nums){
if(nums == null || nums.length < 3 ){
return -1;
}
int maxProdSoFar = 0;
for(int i=0; i<nums.length; i++){
int pivot = nums[i];
int localMax = pivot*getProdOfTwoLargest(nums,i+1,nums.length-1, pivot);
if(localMax > maxProdSoFar){
maxProdSoFar = localMax;
}
}
return maxProdSoFar;
}
public int getProdOfTwoLargest(int[] nums, int startIndex, int endIndex, int pivot){
int firstLargest = -1;
int secondLargest = -1;
// largest has to be in contiguous manner
for (int i=startIndex; i<=endIndex; i++){
if ( (nums[i] > pivot) && (nums[i] > firstLargest)){
secondLargest = firstLargest;
firstLargest = nums[i];
}
}
if(firstLargest == -1 || secondLargest == -1){
return 0;
}
return firstLargest*secondLargest;
}
@vinod
what should be the output for
Input = [1,11,8,9 ,10,14]??
@vinod,
yeah I got you, condition in step14 will be true only for A[i] = 7.
Thanks :)
Consider Input: [1, 11, 12, 7, 8, 9]
Your Output = 1*11*12
Expected Output: 7*8*9
public String removeMultipleSpaces(String word){
if(word == null){
return word;
}
int pivot1 = 0;
int pivot2 = 0;
char[] words = word.toCharArray();
int length = words.length-1;
while (pivot1 <= length){
while (pivot1 <= length && (words[pivot1]) != ' '){
words[pivot2] = words[pivot1];
pivot2++;
pivot1++;
}
if(words[pivot1] == ' '){
words[pivot2] = words[pivot1];
pivot1++;
pivot2++;
}
while (pivot1 <= length && (words[pivot1] == ' ')){
pivot1++;
}
}
String result = String.copyValueOf(words);
return result.substring(0,pivot2);
}
void removeSpaces(char* source){
if(source == NULL)
return;
char* i = source;
char* j = source;
while(*j){
*i = *j++;
if(*i != ' '){
i++;
}
}
*i = '\0';
}
public int indexOfRepeatedBlock(char[] word){
if(word == null || word.length == 0){
return -1;
}
int length = word.length -1;
int finalIndex = 0;
int maxCount = 0;
int startIndex = 0;
int iterator = 1;
while (iterator <= length){
int count = 1;
startIndex = iterator-1;
while (iterator <= length && (word[iterator-1] == word[iterator])){
iterator++;
count++;
}
if(count > maxCount){
maxCount = count;
finalIndex = startIndex;
}
iterator++;
}
return finalIndex;
}
Repbarrietrosado, abc at ABC TECH SUPPORT
Hi, I am Barrie, from Ualapue USA. I believe that every challenge has a solution - and I take great satisfaction ...
- m3th0d.itbhu September 01, 2013