Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [complexity]

Complexity is the analysis of how the time and space requirements of an algorithm vary according to the size of the input. Use this tag for reviews where the "Big O" is a concern.

1
vote
1answer
71 views

Form the largest number by swapping one pair of digits

You are given a number. You are given the opportunity to swap only once to produce the largest number. My approach was to use buckets whose values were their indexes and their locations were their ...
4
votes
2answers
478 views

Time complexity of Max counters

As per the instructions are given in MaxCounters-Codility, You are given N counters, initially set to 0, and you have two possible operations on them: <...
1
vote
1answer
21 views

Time complexity of tape equilibirum

As per the instructions on this Tape Equlibrium-Codility I've written the code ...
2
votes
1answer
79 views

Swift - Finding longest binary gap of a given integer

I recently had the chance to try Codility's algorithm training, and the very first one in the list is finding the longest binary gap of a given integer. I tried to implement this in Swift, and after ...
6
votes
0answers
52 views

Seating Students (partitioning sort of)

The goal of this code is to seat students in a classroom based on a single test score. We want students to be evenly distributed across the class such that every student is positioned next to the ...
1
vote
1answer
43 views

Rearrange an array in place such that the first and last halves are interleaved

Given an array of n elements in the following format { a1, a2, a3, a4, ….., an/2, b1, b2, b3, b4, …., bn/2 }. The task is shuffle the array to {a1, b1, a2, b2, a3, b3, ……, an/2, bn/2 } without ...
0
votes
1answer
117 views

Iteratively determine the diameter of a binary tree

Can the performance of the iterative approach be improved? I find that this approach lags behind many recursive options. no recursive answers, please. Baseline recursive approach: takes 52 steps ...
2
votes
3answers
97 views

Three Numbers in Java

Given three positive numbers A, B, and C. Find the number of positive integers less than D that are divisible by either of A, B or C. Input format The 1st argument given is an Integer A. ...
0
votes
1answer
96 views

Median of two sorted arrays

The task is to find the median of two Arrays. I have an O(n) solution. Can it be written in a better time complexity? ...
1
vote
2answers
80 views

Subset Sums in Java

Given an array of integers, print sums of all subsets in it. Output should be printed in increasing order of sums. Input : arr[] = {2, 3} Output: 0 2 3 5 Input : ...
1
vote
3answers
148 views

Sort all even numbers in ascending order and then sort all odd numbers in Descending order Java

Given an array of integers (both odd and even), the task is to sort them in such a way that the first part of the array contains odd numbers sorted in descending order, rest portion contains even ...
5
votes
5answers
251 views

Sort an array of 0s, 1s and 2s in Java

Write a program to sort an array of 0's,1's and 2's in ascending order. Input: The first line contains an integer 'T' denoting the total number of test cases. In each test cases, First ...
1
vote
1answer
61 views

Finding the horse number you will get

I got this question from the interviewbit site test. There are n horses and you are the kth person in the line to ride on the horse. All the persons in the queue will go with the lowest numbered ...
2
votes
6answers
422 views

Alone in a Couple implementation in Java

In a party everyone is in couple except one. People who are in couple have same numbers. Find out the person who is not in couple. Input: The first line contains an integer \$T\$ denoting ...
5
votes
2answers
96 views

List of Ordered pairs from unordered Pair in Java

Problem statement is Write a method that can take an unordered list of airport pairs visited during a trip and return the list in order. ...
6
votes
1answer
100 views

Moore-Neighbor Tracing Algorithm

I wrote code to extract the contour of a hole, based mostly on the Moore-Neighbor Tracing algorithm. Only a. instead of finding a shape, I'm finding a "hole"; and, b. I'm looking for the (outer) ...
0
votes
1answer
70 views

Reversing the vowels in a String

Given a string, reverse only the vowels present in it and print the resulting string. Input: First line of the input file contains an integer T denoting the number of test ...
2
votes
1answer
102 views

JavaScript Determine if Number is Lucky

A challenge from Code Fights; a function that takes a number no less than 10 and that will always have an even number of digits and determines if the sum of the first half of the digits equals the sum ...
2
votes
1answer
49 views

Anagram checking implementation

Given two strings, check whether two given strings are anagram of each other or not. An anagram of a string is another string that contains same characters, only the order of characters can be ...
1
vote
1answer
49 views

Possible letter combinations of a dial pad in linear time using a recursive approach

Time complexity: I walk the initial unzipped array of keys representing the number O(N) backwards. I then do an inner walk of the proceeding array of letters *O(L^2), mapping it to every value in the ...
4
votes
1answer
119 views

2D Maze solver using recursion in Python

A company I interviewed for sent me a coding problem to solve. The problem was to find a solution to a maze, not necessarily the shortest one. The input would be like so: ...
0
votes
1answer
58 views

Year with the most living (given a list of births and deaths)

I am trying to find the year most people are alive, given a list of births and deaths. I am not sure my approach is optimal or if am calculating the time complexity correctly Break down: I sort the ...
2
votes
2answers
262 views

Determine if Array has an Increasing Sequence

I wrote a function in JavaScript that expects an array of integers (negative or positive) and determines if that array has an increasing sequence. For the sake of better time performance I made the ...
3
votes
2answers
65 views

Non repeating character in Java

Given a string s consisting of lowercase Latin Letters, find the first non repeating character in s. Input: The first line contains T denoting the number of testcases. Then follows ...
1
vote
1answer
102 views

Checking whether two lists contain the same elements

I have two lists of numbers: $$\{i_1, i_2, i_3,i_4\}$$ and $$\{j_1,j_2,j_3,j_4\}$$ The problem I want to solve is: Inside a loop, if the following two conditions are satisfied, then it will do ...
1
vote
2answers
63 views

Star Elements implementation in Java

Given an unsorted array. The task is to find all the star and super star elements in the array. Star are those elements which are strictly greater than all the elements on its right side. Super ...
5
votes
1answer
232 views

Codility: MaxZeroProduct - complexity issues

My solution scored 100% correctness, but 0% Performance. I just can't figure out how to minimize complexity time. Problem: Write a function: ...
3
votes
0answers
40 views

Coordination function

This function started very clean but I had to add requirements: Added a Stopwatch to only update the caller periodically. I guess that responsibility could be ...
1
vote
2answers
140 views

Greater on the right side in Java

Given an array of integers, replace every element with the next greatest element (greatest element on the right side) in the array. Since there is no element next to the last element, replace it ...
0
votes
2answers
231 views

Count the number of occurences of X's within a range in Java

Given an integer X within the range of 0 to 9, and given two positive integers as upper and lower bounds respectively, find the number of times X occurs as a digit in an integer within the ...
1
vote
2answers
67 views

Count total set bits

Im am solving Count total set bits: Find the sum of all bits from numbers 1 to N. Input: The first line of input contains an integer T denoting the number of test cases. The first line ...
0
votes
2answers
52 views

Check if array contains contiguous integers with duplicates allowed in Java

Given an array of n integers(duplicates allowed). Print “Yes” if it is a set of contiguous integers else print “No”. INPUT: The first line consists of an integer T i.e. the number of test ...
1
vote
3answers
243 views

Reverse a sentence in Java

You are given an array of characters arr that consists of sequences of characters separated by space characters. Each space-delimited sequence of characters defines a word. Implement a function ...
4
votes
2answers
204 views

Next palindromic number

I wrote a function that takes a number and finds the next palindromic number. Time complexity is currently O(n2), which is really bad. How could one make this function more efficient? ...
-1
votes
1answer
72 views

For every integer in an array, find the nearest greater integer both before and after it

The given code gives correct output but exceeds the time limit and I have no idea how to optimize it. I know it is of \$O(n^2)\$ complexity but I am not able to get anywhere near to optimizing it. ...
0
votes
1answer
32 views
0
votes
3answers
208 views

Award Budget Cuts implementation in Java

PRAMP Award Budget Cuts The awards committee of your alma mater (i.e. your college/university) asked for your assistance with a budget allocation problem they’re facing. Originally, the committee ...
4
votes
2answers
91 views

Compare Strings

You have been given two strings, A and B (of length N each) and Q queries. The strings contain only 0s and/or 1s. For every query, you are given an index i. You have to update the value at ...
2
votes
2answers
253 views

Program to shorten URL and decode it back to get original URL

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL. Design the encode and ...
1
vote
1answer
183 views

Max Increase to Keep City Skyline in Java

In a 2-dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can ...
0
votes
2answers
165 views

Pancake sort inteview using java

Given an array of integers arr: Write a function flip(arr, k) that reverses the order of the first k elements in the array <...
8
votes
1answer
127 views

Compute the height of a tower made of buckets

I need to speed up my algorithm. It is about finding the height of a tower. The tower is built from buckets. Each bucket has height and radius (1 <= height,radius <= 1000). Variable ...
1
vote
1answer
47 views

Algorithmic complexity of this algorithm to find all ordered permutations of length X

I have written a recursive function to generate the list of all ordered permutations of length X for a list of chars. For instance: ['a', 'b', 'c', 'd'] with X=2 will give [['a', 'a'], ['a', 'b'], ['...
3
votes
0answers
182 views

Finding the majority element in a sequence of integers in \$O(n \log n)\$

I wrote this piece of code as solution to a problem set that required finding the majority element in a list using divide and conquer in \$ O(n \log n)\$. The majority element is defined as the ...
4
votes
2answers
185 views

Merge non overlapping intervals

Merge Intervals Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their ...
5
votes
0answers
239 views

Intersection of two lists in Python

I am currently working on an algorithm, which involves finding the intersection of two lists. That is, given the following inputs [1,2,2,1],...
2
votes
4answers
316 views

Reverse the digits of an Integer

Reverse digits of an integer. Example1: x = 123, return 321 Example2: x = -123, return -321 Return 0 if the result overflows and does not fit in a 32 bit signed integer This is my approach: <...
4
votes
1answer
110 views

“Tara's Beautiful Permutations” challenge

I'm practising my coding skills using Python to answer medium to difficult problems on sites like HackerRank. Here is the challenge. Given an array of integers, where each number can appear at most ...
1
vote
1answer
105 views

Hackerrank “Breaking the Record” solution

I have solved the hacker rank problem listed here. Given a sequence of scores, I need to count the number of times the records for the high and low scores have been broken. Easiest way for me was to ...
3
votes
1answer
49 views

Compute leaderboard of competitive riders throughout a season

I have a table in my DB that contains Riders as rows and their points throughout the season as columns. Here are the columns: ...