# 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.

392 questions
Filter by
Sorted by
Tagged with
1answer
65 views

### Searching for a sum of any series in array

I'm given this method, and requested to analyze what it does, and minimize its complexity (both time and space). All values are known to be larger than zero. ...
1answer
847 views

### Vertex Cover Problem Greedy Solution [closed]

As far as I understood this problem, it is a subset of vertices of Graph G, such that every edge has at least one endpoint in the subset. This problem is considered to be NP Complete. However I think ...
0answers
210 views

### MergeSort linked list implementation

I wrote a MergeSort implementation of doubly linked list, based on the MergeSort implementation of array on the textbook Algorithms 4th, which is definitely $O(n \log n)$. I think my linked list ...
1answer
542 views

### Implementing components(separatedBy:) method in Swift

On looking at the components(separatedBy separator: String) -> [String] method from the Swift Standard Library, I tried to come up with an implementation just ...
2answers
69 views

### Unbalanced Binary Search Tree insertion and search with random and sorted values

I have created this unbalanced binary search tree in C. Can anyone say this is a true approach or not? I have two scenarios for insertion and search: in the first scenario I am inserting 10000 random ...
2answers
179 views

### Substrings search (Aho-Corasick algorithm)

I have a code where the goal is to give score to strings based on how much score certain substrings are worth (including repeating substrings). The way my code (which is based on the Aho-Corasick ...
1answer
1k views

### “Counter Game” Powers of 2 Game

I have been working on this hackerrank problem: Louise and Richard have developed a numbers game. They pick a number (1 ≤ n < 264) and check to see if it is a power of 2. If it is, they divide ...
0answers
174 views

### Codility Tape Equilibrium

This question is related to this one, since it's about the same Codility exercise (Tape Equilibrium instructions): Time complexity of tape equilibirum Basically, given an integer array, the objective ...
2answers
44 views

### Incrementing specified list values, with “catch-up” [closed]

I completed a coding challenge recently in which my function was to be given two parameters: N, the number of counters to be used (numbered 1 through N) - and A, an array of integers. Iterating ...
0answers
36 views

### Mixed Duo String Generator Part 2

Mixed Duo String Generator Hello again; Previously my code was critique and I applied this feedback to form my new revised code for the Mixed Duo String Generator. In the code below I revised it to ...
3answers
67 views

### Mixed Duo String Generator 2 [duplicate]

I've create a program that finds mixed duo within a string. It removes characters from a string that do not form the first mixed duo. It does not rearrange the order of the string, it ony remove ...
1answer
420 views

### Find maximum in sorted and rotated array

This is an interview question. A sorted rotated array is a sorted array which was rotated 0 or more times. For example: [1,2,3] -> [2,3,1] ...
2answers
72 views

### Place arithmetic signs in correct order to get the number

Given a list of numbers, place signs + or - in order to get the required number. If it's possible then return ...
1answer
81 views

### O(n) Object Pool

I recently rewrote my object pool design to $O(n)$ complexity. I did this using a linked list, which is not native in JavaScript. It does not, unfortunately, automatically assign ...
1answer
73 views

### Given an array of positive integers, find shortest subarray whose sum exceeds a threshold [closed]

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead. Example: Input: ...
0answers
41 views

### Find target in sorted array pivoted at some unknown point in O(log n)

You are given an array sorted in ascending order which is rotated at some pivot unknown to you beforehand. Find your target in $O(log n)$ which means it should be a binary search. If the value ...
1answer
916 views

### Median of two sorted arrays JavaScript

Trying to find the median of two sorted arrays in O(log(m+n)) or better. I believe this is O(log(m+n) or O(log(m)) or O(n). ...
1answer
81 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 ...
1answer
865 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: <...
1answer
41 views

### Time complexity of tape equilibirum

As per the instructions on this Tape Equlibrium-Codility I've written the code ...
1answer
1k 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 ...
1answer
1k 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 ...
1answer
204 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 ...
1answer
685 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 ...
3answers
118 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. ...
1answer
1k 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? ...
2answers
314 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 : ...
3answers
4k 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 ...
5answers
2k 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 ...
1answer
75 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 ...
6answers
622 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 ...
2answers
664 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. ...
1answer
610 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) ...
1answer
365 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 ...
1answer
1k 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 ...
1answer
137 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 ...
1answer
111 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 ...
1answer
4k 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: ...
1answer
193 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 ...
2answers
620 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 ...
2answers
300 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 ...
2answers
155 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 ...
2answers
368 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 ...
1answer
756 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: ...
0answers
54 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 ...
2answers
198 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 ...
2answers
2k 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 ...
2answers
83 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 ...
2answers
1k 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 ...
3answers
882 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 ...